2.2 函數與關係

有序對 $(x,y)$ 記錄從 $X$ 中元素到 $Y$ 中元素的有向聯繫。把這些聯繫收集起來， 便得到笛卡兒積 $X\times Y$ 的一個子集。 有些聯繫為每個輸入指定唯一輸出，有些容許多個輸出或沒有輸出；集合語言能精確區分這些情況。

定義

關係

$X$ 與 $Y$ 之間的關係，是 $X \times Y$ 的任何子集。

如果 $X = Y$，便稱為 $X$ 上的關係。

函數是特別的關係

定義

函數

由 $X$ 到 $Y$ 的函數，是 $X \times Y$ 的一個子集，並且要求 $X$ 中每個 $x$ 都只會配對到 $Y$ 中唯一一個 $y$。

同一件事可以用幾種方式去讀：

• $X$ 是定義域（domain），即輸入集合。
• $Y$ 是目標集合（codomain），即容許輸出所在的集合。
• $f$ 的圖像（graph）是 $\{(x,f(x)):x\in X\}$，即由輸入 $x\in X$ 與對應輸出 $f(x)$ 組成的有序對集合。
• 像（image）由實際取得的輸出組成。
• 原像（preimage）由映入指定輸出集合的輸入組成。

常見錯誤

函數不可以令一個輸入對應多個輸出

關係可以令一個輸入連到多個輸出，但函數不可以。每個輸入都必須有且只有一個輸出。

如何檢驗一個候選圖像

子集 $\Delta \subset X \times Y$ 是函數 $X\to Y$ 的圖像，當且僅當每個 $x\in X$ 都恰好出現在一個有序對 $(x,y)\in\Delta$ 中。漏掉輸入違反 「存在」，同一輸入對應兩個不同輸出則違反「唯一」。例如以下 $\Delta=\{(n+10,n):n\in\mathbb N\}\subset\mathbb N\times\mathbb Z$ 漏掉輸入 $0$，因為 $n+10=0$ 要求 $n=-10$；所以它不是由 $\mathbb N$ 到 $\mathbb Z$ 的函數圖像。若改為 $n\in\mathbb Z$，每個 $x\in\mathbb Z$ 都有唯一 $n=x-10$，便是由 $\mathbb Z$ 到 $\mathbb Q$ 的函數圖像。$\{(x^2,x^3):x\in\mathbb Q\}$ 則既漏掉負輸入，又有 $(1,1)$ 和 $(1,-1)$ 兩個輸出，不能成為函數圖像。

常見錯誤

定義域會受語境影響

$1/x$ 不是一個不加限定就完整的函數。它可以是 $R \setminus \{0\}$ 上的函數， 或者 $Q \setminus \{0\}$ 上的函數；但無論如何，也不可以包含 $0$。

所有函數所組成的集合

當函數已經被定義為有序對集合後，我們亦可以建立「以函數為元素」的集合。 若 $A$ 與 $B$ 是集合，記號

$$B^A$$

表示所有由 $A$ 到 $B$ 的函數所組成的集合。

這個記號不是偶然的。若 $A$ 有 $n$ 個元素，而 $B$ 有 $m$ 個元素，一個 $A \to B$ 的函數就是替 $A$ 的每個輸入各選一個 $B$ 中的輸出。因此共有 $m^n$ 個這樣的函數。例如 $A = \{a,b,c\}$、$B=\{0,1\}$ 時，$B^A$ 有 $2^3=8$ 個函數。這正是 $|P(A)| = 2^{|A|}$ 背後的同一個計數原理。 若 $A$ 為空集，則恰有一個空函數，即使 $B$ 亦為空集也一樣；這裏採用組合計數中的約定 $0^0=1$。

例題

把 $B^A$ 讀成函數集合

令 $A=\{a,b\}$、$B=\{0,1\}$。那麼 $B^A$ 恰有四個函數：

$$\begin{array}{c|cc} & a & b \\ \hline f_1 & 0 & 0\\ f_2 & 0 & 1\\ f_3 & 1 & 0\\ f_4 & 1 & 1 \end{array}$$

每一行是一整個函數，而不是某一個函數的一個值。

如何仔細閱讀一個函數

例題

平方函數會有重複輸出

考慮由 $f(x)=x^2$ 定義的函數 $f:\mathbb R\to\mathbb R$。

那麼 $f(-2) = 4$ 與 $f(2) = 4$，也就是不同輸入可以有同一個輸出。這是允許的。

不允許的是同一個輸入有兩個不同輸出。

例如，把 $y^2 = x$ 視為由 $x$ 到 $y$ 的規則時，$x = 4$ 會有 $y = 2$ 與 $y = -2$，所以不是函數。

函數的圖像 是一個非常特別的積集子集：每一條垂直線在可行的輸入位置恰好相交一次。

像、原像與合成

對 $f : X \to Y$，「像」這個詞有三種相關但不同的用法：

• $f(x)$ 是單一輸入 $x$ 的像。
• 若 $A \subset X$，則 $f(A) = \{f(x) \mid x \in A\}$ 是集合的像。
• $f(X)$ 是整個函數的像，即實際出現過的輸出。

對 $B\subseteq Y$，原像定義為

$$f^{-1}(B) = \{x \in X \mid f(x) \in B\}.$$

即使 $f$ 沒有反函數，$f^{-1}(B)$ 仍然有意義。

設 $f:X\to Y$、$g:Y\to Z$，合成是函數 $g\circ f:X\to Z$，定義為

$$(g \circ f)(x) = g(f(x)).$$

次序很重要：$g \circ f$ 也就是「先做 $f$，再做 $g$」。

例題：計算函數合成

設 $f,g,h:\mathbb R\to\mathbb R$ 分別為 $f(x)=x+1$、$g(x)=x^2$、 $h(x)=x-7$。直接代入得到

$$\begin{aligned} f\circ f&:x\mapsto x+2, & f\circ g&:x\mapsto x^2+1, & f\circ h&:x\mapsto x-6,\\ g\circ f&:x\mapsto (x+1)^2, & g\circ g&:x\mapsto x^4, & g\circ h&:x\mapsto (x-7)^2,\\ h\circ f&:x\mapsto x-6, & h\circ g&:x\mapsto x^2-7, & h\circ h&:x\mapsto x-14. \end{aligned}$$

最右邊的函數先作用。

像與原像的集合恆等式

設 $f:X\to Y$、$A,B\subset X$、$C,D\subset Y$。像滿足

$$f(A\cup B)=f(A)\cup f(B),\qquad f(A\cap B)\subset f(A)\cap f(B)$$

第一式的兩個包含可由元素追蹤得到：若 $y\in f(A\cup B)$，就存在 $x\in A\cup B$ 使 $f(x)=y$。因此 $x\in A$ 或 $x\in B$，從而 $y\in f(A)\cup f(B)$。反過來，若 $y\in f(A)\cup f(B)$，就存在 $x\in A$ 或 $x\in B$ 使 $f(x)=y$。這個 $x$ 屬於 $A\cup B$， 所以 $y\in f(A\cup B)$。 第二式的包含同理，但等號可能失敗。取 $X=\{1,2\}$、$Y=\{0\}$、 $f(1)=f(2)=0$、$A=\{1\}$、$B=\{2\}$，左邊是空集而右邊是 $\{0\}$。

原像保留聯集與交集：

$$f^{-1}(C\cup D)=f^{-1}(C)\cup f^{-1}(D),\qquad f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D).$$

$x\in f^{-1}(C\cup D)$ 當且僅當 $f(x)\in C$ 或 $f(x)\in D$，也就是 $x\in f^{-1}(C)\cup f^{-1}(D)$。反向閱讀便證明另一個包含；交集則把「或」 改為「且」。若補集分別取在目標 $Y$ 與定義域 $X$ 中，還有

$$f^{-1}(C\setminus D)=f^{-1}(C)\setminus f^{-1}(D),\qquad f^{-1}(Y\setminus C)=X\setminus f^{-1}(C)$$

第一式的條件是 $f(x)\in C$ 且 $f(x)\notin D$；第二式清楚標明兩個 補集所依據的全集。

例題

比較 $f(x)=x^2$ 的像與原像

設 $f : R \to R$ 由 $f(x) = x^2$ 定義，而

$$A = \{-2, -1, 0, 1, 2\}, \qquad B = \{0, 1, 4\}.$$

那麼

$$f(A) = \{0, 1, 4\}.$$

而且

$$f^{-1}(B) = \{-2, -1, 0, 1, 2\},$$

每個列出的點都映入 $B$。反過來，若 $x^2\in\{0,1,4\}$，則 $x^2=0$、$x^2=1$ 或 $x^2=4$。分別因式分解得 $x=0$、$x=\pm1$ 或 $x=\pm2$，所以沒有其他實數原像。

如果改用 $C = \{4\}$，就有

$$f^{-1}(C) = \{-2, 2\}.$$

單射、滿射、雙射

定義

三個常用詞

• 單射：不同輸入的像互不相同。
• 滿射：目標集合每個值都會被取到。
• 雙射：同時單射與滿射。

等價說法也很有用：

• $f$ 是單射，當且僅當對任意 $x_1,x_2\in X$，$f(x_1)=f(x_2)$ 都蘊含 $x_1=x_2$。
• $f$ 是滿射，當且僅當 $f(X)=Y$。
• $f$ 是雙射，當且僅當每個目標值都恰好被一個輸入取到。

例題：直接判斷單射與滿射

首先，$X=\{0,1,3,5\}$、$Y=\{5,7,11\}$ 的函數中，$5$ 由兩個輸入取得， 所以不是單射。完整給定值是 $f(0)=7$、$f(1)=5$、$f(3)=11$、 $f(5)=5$；$5,7,11$ 都出現，故是滿射。

其次，對 $f(x)=x^5+3x+1$（定義域 $\{-2,-1,0,1,2\}$，目標集合 $\mathbb Z$），五個輸出是

$$f(-2)=-37,\quad f(-1)=-3,\quad f(0)=1,\quad f(1)=5,\quad f(2)=39$$

它們互不相同，所以是單射；例如 $0$ 不在像中，所以不是滿射。

最後，$f:\mathbb Z\to\mathbb Z$、$f(x)=x^2+x$ 不是單射，因為 $f(0)=f(-1)=0$；它也不是滿射，因為 $x(x+1)$ 必為偶數，不能取得奇數。

用箭頭區分定義

箭頭圖可以顯示唯一輸出、碰撞，以及 目標集合是否被覆蓋。

用同一張箭嘴圖分清 domain、target、image、preimage、單射、滿射與合成。

1. domain 與 target

   函數 f:X->Y 是一種關係，其中 X 內每個輸入在 target Y 中都有唯一一個輸出。

2. graph 作為有序對

   graph 把同一批箭嘴記成 X x Y 內的有序對，而且每個輸入只出現在一個有序對中。

3. image 與 preimage

   image 是向前讀到被命中的輸出；preimage 是從輸出集合反向讀回會落入其中的輸入。

4. 單射

   單射表示沒有碰撞：若兩個輸入有同一輸出，它們其實必須是同一個輸入。

5. 滿射

   滿射表示實際 image 等於整個 target，因此沒有 target 元素被漏掉。

6. 合成

   對 g o f，要先做 f，再把得到的輸出放入 g。

同一張箭嘴圖可以把主要定義分清楚。函數要求每個輸入剛好有一個輸出；單射禁止碰撞；滿射覆蓋 target；合成則把一個輸出接到下一個映射。

定理

反函數存在當且僅當雙射

對函數 $f : X \to Y$，反函數存在，當且僅當 $f$ 是雙射。

證明：為甚麼雙射會有逆

如果 $f$ 是單射又滿射，那麼對每個 $y \in Y$ 都存在唯一一個 $x \in X$ 使 $f(x)=y$。

這個唯一性讓我們可以定義一個新函數 $g : Y \to X$，令 $g(y)$ 就是滿足 $f(x)=y$ 的唯一 $x$。

按定義，$g(f(x)) = x$ 與 $f(g(y)) = y$，所以 $g$ 就是 $f$ 的反函數。

證明：反函數唯一性與存在性

若 $g,h:Y\to X$ 都是 $f:X\to Y$ 的反函數，則

$$g=g\circ id_Y=g\circ(f\circ h)=(g\circ f)\circ h=id_X\circ h=h$$

所以反函數若存在便唯一。若 $f:X\to Y$、$g:Y\to Z$、$k:Z\to W$， 對每個 $x\in X$ 有

$$k\circ(g\circ f)(x)=k(g(f(x)))=(k\circ g)\circ f(x)$$

因此合成滿足結合律。下文關於反函數蘊含關係的證明將說明必要性：有反函數就必為雙射；上面的構造則給出雙射的反函數。

例題

單射與非單射例子

$n \mapsto n + 1$（定義在 $Z$ 上）是單射亦是滿射，所以是雙射。

$x \mapsto x^2$（定義在 $R$ 上）不是單射，因為 $1$ 與 $-1$ 有同一個像。

$x \mapsto e^x$（定義在 $R$ 上）是單射，但不是滿射到 $R$，因為它不能取到非正數。

常見錯誤

不要將原像與反函數混淆

$f^{-1}(B)$ 表示原像，只要 $B$ 是目標集合的子集就有意義。反函數 $f^{-1}$ 則只在 $f$ 為雙射時存在。

左逆與右逆

對 $f:X\to Y$，兩個逆映射等式的定義域不同：

• 左逆 $h:Y\to X$ 滿足 $h \circ f = id_X$。
• 右逆 $g:Y\to X$ 滿足 $f \circ g = id_Y$。

一般情況下，兩者不一定相同。

例題

一個有左逆但沒有右逆的映射

設 $X = \{a, b, c\}$，$Y = \{α, β, γ, δ\}$。定義

$$f_1(a)=α,\qquad f_1(b)=β,\qquad f_1(c)=γ.$$

這個映射是單射但不是滿射，因為 $δ$ 沒有被取到。 所以它可以有左逆，但不可以有右逆。

例如定義 $h : Y \to X$：

$$h(α)=a,\qquad h(β)=b,\qquad h(γ)=c,\qquad h(δ)=a.$$

那麼就有 $h \circ f_1 = id_X$。

缺少輸出 $δ$ 排除了 $f_1\circ g=id_Y$，所以沒有右逆。

例題

一個有右逆但沒有左逆的映射

定義 $f_2 : Y \to X$ 如下：

$$f_2(α)=a,\qquad f_2(β)=a,\qquad f_2(γ)=b,\qquad f_2(δ)=c.$$

這個映射是滿射但不是單射，所以可以有右逆但沒有左逆。

一個右逆是 $g : X \to Y$，令

$$g(a)=α,\qquad g(b)=γ,\qquad g(c)=δ.$$

那麼就有 $f_2 \circ g = id_X$。

碰撞 $f_2(α)=f_2(β)$ 排除了左逆。

定理

有限自映射：有左逆已足以推出可逆

設 $X$ 是有限集合，且 $g : X \to X$。如果存在 $h : X \to X$ 滿足 $h \circ g = id_X$，那麼 $g$ 是雙射，而且 $h$ 亦是 $g$ 的右逆。

證明：有限自映射有左逆時可逆

等式 $h \circ g = id_X$ 首先說明 $g$ 是單射：若 $g(x_1)=g(x_2)$，兩邊 再作用 $h$，就得到 $x_1=x_2$。

對有限集合而言，由 $X$ 到自身的單射必然也是滿射。因此 $g$ 有雙側反函數 $g^{-1}$。 由 $h\circ g=id_X$，

$$h=h\circ id_X=h\circ(g\circ g^{-1})=(h\circ g)\circ g^{-1}=g^{-1}.$$

因此亦有 $g\circ h=id_X$。當 $X$ 為空集時，唯一的自映射是空函數，上述結論仍成立。

證明：逆映射的蘊含及其逆向構造

設 $f:X\to Y$、$h:Y\to X$。若 $h\circ f=\operatorname{id}_X$，則 $f(x)=f(x')$ 推出 $x=h(f(x))=h(f(x'))=x'$，所以有左逆必為單射。若 $f\circ h=\operatorname{id}_Y$，每個 $y$ 都等於 $f(h(y))$，所以有右逆必為滿射。

反過來，設 $f$ 單射且 $X\ne\varnothing$。固定一個 $x_0\in X$；當 $y\in f(X)$ 時令 $h(y)$ 為唯一原像，否則令 $h(y)=x_0$。這給出左逆，不需要選擇公理，因為像外只需使用同一個固定值。若 $X=\varnothing$ 而 $Y$ 非空，空集到 $Y$ 的單射沒有左逆，因為不存在 $Y\to\varnothing$ 的映射。若兩者皆空，空映射就是自己的逆。

對滿射，構造右逆要在每個纖維 $f^{-1}(\{y\})$ 中選一個元素。明確構造的選擇或有限次選擇不需要一般選擇公理；斷言每個任意滿射都有右逆則使用選擇公理。這與雙射的唯一原像不同，後者無需這樣的選擇原則。

例題

具有完整左逆的無限包含映射

令 $i:\mathbb N\to\mathbb Z$ 為 $i(n)=n$，其中 $0\in\mathbb N$。定義 $h:\mathbb Z\to\mathbb N$：當 $z\ge0$ 時取 $h(z)=z$，當 $z<0$ 時取 $h(z)=0$。對每個 $n$ 都有 $h(i(n))=n$。但 $i$ 沒有右逆，因為負整數（例如 −1）在 $i$ 下沒有原像。

不要求唯一輸出的關係

函數要求每個輸入恰有一個輸出。去掉這個限制，就能用關係比較次序、整除或共同性質， 而不必為每個輸入挑選一個輸出。

寫 $xRy$ 也就是 $(x, y) \in R$。

對 $R \subset X \times Y$：

• 定義域是所有至少與一個 $y\in Y$ 相關的 $x\in X$ 所組成的集合。
• 像（或值域）是所有至少與一個 $x\in X$ 相關的 $y\in Y$ 所組成的集合。

例題

關係未必是函數

設 $X$ 是國家集合，$Y$ 是城市集合。

「$y$ 是 $x$ 的首都」這個關係是 $X \times Y$ 上的關係。它是否函數，要看時代與國家。

$y^2 = x$（定義在 $Z \times Z$ 上）也是關係，但如果視為由 $x$ 到 $y$ 的規則，就不是函數， 因為一個輸入可以有多個輸出。

關係可以處理「有連結，但不要求唯一性」這種情況。順序與等價類之後都要用到這個語言。

同一個集合上的關係

$X \times X$ 上的關係尤其重要。

定理

四個常用性質

一個 $X$ 上的關係可以有以下性質；各條件須對 $X$ 中所有相應元素成立：

• 自反（reflexive）：對每個 $x$，都有 $xRx$。
• 對稱（symmetric）：$xRy$ 蘊含 $yRx$。
• 反對稱（antisymmetric）：若 $xRy$ 且 $yRx$，則 $x=y$。
• 傳遞（transitive）：若 $xRy$ 且 $yRz$，則 $xRz$。

兩種特別重要的關係是：

• 偏序（partial order）滿足自反、反對稱和傳遞性。
• 等價關係（equivalence relation）滿足自反、對稱和傳遞性。

關係性質與反例

令 $X=\mathcal P(\{1,2,3,4\})$，並以 $x\cap y=\varnothing$ 定義 $xRy$。 它不是自反，因為非空集合 $\{1\}$ 與自身的交集不為空；它是對稱， 因為交集滿足交換律；它不是傳遞，取 $x=\{1\}$、$y=\varnothing$、 $z=\{1\}$，則 $xRy$ 且 $yRz$，但不滿足 $xRz$；它也不是反對稱， 因為 $\{1\}R\{2\}$ 且 $\{2\}R\{1\}$，而兩個集合不相等。

再檢驗以下整數上的關係：

• $x-y$ 為奇數不是自反，因為 $x-x=0$；它雖然對稱，卻不傳遞， 例如 $0R1$、$1R2$，但 $0$ 不與 $2$ 相關。
• $x+y$ 為偶數是等價關係。自反及對稱顯然；若 $x+y$ 與 $y+z$ 都是偶數， 則 $(x+z)=(x+y)+(y+z)-2y$ 也是偶數。等價類是偶數類與奇數類。
• $x+y=0$ 不是自反（除 $0$ 之外），也不傳遞：$1R(-1)$、 $(-1)R1$，但 $1$ 不與自身相關。
• $x|y|=|x|y$ 是自反及對稱，因為它等價於「兩個整數同號，或至少 一個為零」。但它不傳遞：$1R0$ 且 $0R(-1)$，而 $1$ 不與 $-1$ 相關。 因此它不是等價關係，也沒有等價類可列出。

這些反例說明，判斷等價關係必須逐項檢驗自反、對稱、傳遞三個條件。

對稱與反對稱描述不同的條件：

• 對稱要求每一條關係箭頭都有反向箭頭。
• 反對稱要求互有箭頭的兩個元素相等。

例題

整除關係是偏序

在正整數 $\mathbb Z_{\gt0}$ 上寫 $a \mid b$ 表示 $a$ 整除 $b$。

這個關係滿足自反性，因為每個數都整除自己。 它滿足反對稱性，因為如果 $a \mid b$ 與 $b \mid a$，在正整數之中就有 $a = b$。 它亦滿足傳遞性，因為整除可以沿鏈傳遞。

所以整除是偏序。

這裏必須限定正整數。在全體整數上，$1\mid-1$ 且 $-1\mid1$，但 $1\ne-1$，所以反對稱性會失敗。

偏序不只是一個名詞。它幫我們整理「包含」「細化」「整除」這些有結構的關係。

例題

子集關係作為一個小型偏序

令 $X=\{a,b\}$，並考慮 $P(X)$，即 $X$ 的所有子集所組成的集合。 用包含關係排列 $P(X)$。

最底層元素是 $\varnothing$，最頂層元素是 $\{a,b\}$，中間兩個元素是 $\{a\}$ 和 $\{b\}$。直接相鄰的覆蓋關係 只有

$$\varnothing \subset \{a\},\quad \varnothing \subset \{b\},\quad \{a\}\subset \{a,b\},\quad \{b\}\subset \{a,b\}.$$

Hasse 圖只畫這些直接覆蓋關係；較長的比較則由傳遞性自動理解。

例題

一個簡單的等價關係

對正整數 $m$，模 $m$ 同餘是 $Z$ 上的等價關係：兩個整數有相同餘數時相關。模 $3$ 時， 整數分成餘數為 $0$、$1$、$2$ 的三類，這些類分割整個 $Z$。

證明：模 $m$ 同餘

固定 $m\in\mathbb Z$ 且 $m\gt0$。定義 $a\equiv b\pmod m$ 當且僅當 $m\mid(a-b)$。它是 $\mathbb Z$ 上的等價關係：$m\mid0$ 給出自反性； 若 $m\mid(a-b)$，則 $m\mid(b-a)=-(a-b)$，給出對稱性；若 $m\mid(a-b)$ 且 $m\mid(b-c)$，則 $m$ 整除兩者之和 $a-c$，給出傳遞性。

其等價類為

$$[a]_m=\{b\in\mathbb Z:m\mid(a-b)\}$$

也就是相同餘數的整數所組成的剩餘類。

等價類與商集

模 $3$ 時，整數 $1$、$4$、$-2$ 的餘數相同。它們是不同的整數，但同餘關係不區分 它們相差的 $3$ 的倍數。如果只保留餘數資訊，就需要一個對象代表這些彼此等價的整數。

用 $1$ 作標籤很方便，但改用 $4$ 不應改變所代表的對象。把所有與 $1$ 相關的整數 收集成一個集合，便滿足這個要求：改用 $4$ 得到的仍是同一個集合。等價類把這種 不依賴代表元的性質落實到新對象的構造中。

一般關係未必有此性質：兩個元素對應的集合可能相交而不相等。自反性、對稱性和傳遞性 排除了這種含糊情況。下面的劃分定理說明，等價關係的類為何能成為彼此分開的新對象。

定義

等價類

設 $R$ 是 $X$ 上的等價關係。對 $x \in X$， $x$ 的等價類定義為

$$[x]_R = \{y \in X \mid yRx\}.$$

定義

商集

如果 $\sim$ 是 $X$ 上的等價關係，那麼所有等價類組成的集合記作 $X / \sim$。

定理

等價類會分割集合

如果 $R$ 是 $X$ 上的等價關係，那麼等價類會覆蓋整個集合，而且任何兩個等價類只會相等或者互相不相交。

證明：相交的等價類相等

自反性給出 $xRx$，所以每個 $x\in X$ 都屬於 $[x]_R$，等價類覆蓋 $X$。

設 $z\in[x]_R\cap[y]_R$，則 $zRx$ 且 $zRy$。若 $u\in[x]_R$，有 $uRx$；由對稱性得 $xRz$，再由傳遞性得 $uRz$ 及 $uRy$。因此 $u\in[y]_R$，證明 $[x]_R\subseteq[y]_R$。

反過來，若 $v\in[y]_R$，有 $vRy$；對稱性給出 $yRz$，傳遞性依次給出 $vRz$ 和 $vRx$，故 $v\in[x]_R$，證明 $[y]_R\subseteq[x]_R$。兩個包含關係推出相等。因此不相等的等價類不能相交，各個不同的等價類構成 $X$ 的分割。

整數構造和 有理數構造會把這套方法 用於有序對。構成等價類之後，定義算術還須另作檢驗：改用不同代表元，是否仍得到同一個 輸出類？劃分定理建立新對象，良定義性則保證這些對象上的運算有確定意義。

用雙射比較集合

基數表示大小，但在集合論中，正確的大小比較不一定只是普通計數。兩個集合 $X$ 和 $Y$ 同勢，意思是它們之間存在一個雙射：

$$|X| = |Y| \quad \text{表示存在一個雙射 } X \to Y.$$

有限集合中，這與元素個數一致；無限集合中則需要更謹慎地比較。

例題

$N$ 與 $Z$ 之間的第一個雙射

$$0, 1, -1, 2, -2, 3, -3, \ldots$$

這對應到一個函數 $f : N \to Z$，例如

$$f(0)=0,\qquad f(2k+1)=k+1,\qquad f(2k+2)=-(k+1).$$

每個整數都恰好出現一次，所以這是一個雙射枚舉。

例題

從 $N \times N$ 到 $N$ 的一個單射

自然數對可以編碼成自然數。例如，定義

$$F(m,n)=2^m3^n.$$

這確實定義了一個函數 $F : N \times N \to N$，因為對每個 $(m,n)$， $2^m3^n$ 都是自然數。

要證 $F$ 是單射，假設

$$F(m,n)=F(m',n').$$

也就是

$$2^m3^n = 2^{m'}3^{n'}.$$

唯一素因數分解說明，一個正整數分解成素數冪的方式只有一種。因此兩邊的 $2$ 的指數必須相同，$3$ 的指數亦必須相同：

$$m=m', \qquad n=n'.$$

所以兩個不同有序對不可能被送到同一個自然數。

後面的基數筆記 將進一步研究無限集合的大小比較。

用函數組合元素

函數也可以定義運算：輸入同一集合中若干元素組成的元組，輸出仍在該集合中。 寫清這個函數類型，便同時明確了輸入個數和輸出的封閉性。

定義

把運算讀成函數

集合 $S$ 上的一個 $n$ 元運算，是一個函數

$$S^n \to S.$$

例如加法是二元運算，因為它取一對輸入，並回傳同一個集合中的一個輸出。

當 $n=0$ 時，$S^0$ 是只包含空元組的單元素集合。因此 $S^0\to S$ 的函數就是 在 $S$ 中指定一個元素；若 $S$ 為空集，這樣的函數不存在。 么半群與群 將研究二元運算及其可能滿足的定律。

常見錯誤

常見錯誤

對稱不等於反對稱

實數上的 $≤$ 是反對稱但不是對稱。等號是對稱又反對稱，而正整數 $\mathbb Z_{\gt0}$ 上的整除是反對稱但不是對稱。

常見錯誤

關係不構成函數的兩種情況

它可以令同一個輸入對應多個輸出，亦可以令某些輸入完全沒有輸出。

小檢查

思考檢查

$x ≤ y$ 在實數上是關係嗎？是函數嗎？

先問它是不是 $R \times R$ 的子集，再問每個輸入有沒有唯一輸出。

解答 · 答案

它是關係，因為它是 $R \times R$ 的子集；但它不是函數，因為同一個輸入 $x$ 可以對應許多個 $y$。

思考檢查

$f^{-1}(B)$ 在 $f$ 不是雙射時還有沒有意義？

分清原像與反函數。

解答 · 答案

有。原像永遠有意義。

思考檢查

如果 $A$ 有三個元素，而 $B$ 有兩個元素，$B^A$ 中有多少個函數？

對 $A$ 的每個輸入，各自在 $B$ 中選一個輸出。

解答 · 答案

共有 $2^3 = 8$ 個函數。

思考檢查

若 $g : X \to X$ 有左逆且 $X$ 是有限集合，證明 $g$ 可逆時第一步應證明 $g$ 有甚麼性質？

使用等式 $h \circ g = id_X$。

解答 · 答案

先證 $g$ 是單射。由於 $X$ 有限，單射推出滿射，因此 $g$ 是雙射。

思考檢查

為甚麼 $F(m,n)=2^m3^n$ 定義了由 $N \times N$ 到 $N$ 的單射？

留意素數 $2$ 和 $3$ 的指數。

解答 · 答案

如果 $2^m3^n = 2^{m'}3^{n'}$，唯一素因數分解會迫使 $m=m'$ 且 $n=n'$。 因此相同輸出推出相同有序對，所以 $F$ 是單射。

思考檢查

如果一個關係滿足自反性、對稱性和傳遞性，它叫甚麼？

回想會將集合劃分成等價類的關係。

解答 · 答案

它是等價關係。