2.2 函數與關係

函數與關係把積集變成有結構的數學對象：函數要求輸出唯一，關係記錄一般的聯繫。

函數是特別的關係

定義

函數

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

這就是本單元採用的集合論定義。

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

• $X$ 是 domain，即輸入集合。
• $Y$ 是 target，即可能輸出的集合。
• $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)$ 兩個輸出，不能成為函數圖像。

常見錯誤

domain 會受語境影響

$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|\}$ 背後的同一個計數原理。

例題

把 $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(-2) = 4$ 同 $f(2) = 4$，也就是不同輸入可以有同一個輸出。這個是允許的。

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

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

函數的 graph 是一個非常特別的積集子集：每一條垂直線在可行的輸入位置只會撞到一次。

像、原像與合成

對 $f : X \to Y$，本課程中會用 image 這個詞說明三件相關但不同的事：

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

原像定義為

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

就算 $f$ 沒有逆函數，$f^\{-1\}(B)$ 仍然有意義。

合成定義為

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

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

例題：計算函數合成

對 $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)$ 時，其原像在 $A$ 或 $B$；反過來，$f(A)$ 或 $f(B)$ 中的原像都在 $A\cup B$。 第二式的包含同理，但等號可能失敗。取 $X=\{1,2\}$、$Y=\{0\}$、 $f(1)=f(2)=0$、$A=\{1\}$、$B=\{2\}$，左邊是空集而右邊是 $\{0\}$。

原像保留並集與交集：$x\in f^{-1}(C\cup D)$ 當且僅當 $f(x)\in C$ 或 $f(x)\in 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$；第二式清楚標明兩個 補集所使用的 ambient set。

例題

比較 $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$ 單射 iff $f(x1) = f(x2)$ 蘊含 $x1 = x2$
• $f$ 滿射 iff $f(X) = Y$
• $f$ 雙射 iff 每個目標值都剛好被命中一次

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

首先，$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)$ 必為偶數，不能取得奇數。

用箭嘴區分定義

箭嘴圖可以顯示唯一輸出、碰撞，以及 target 是否被覆蓋。

用同一張箭嘴圖分清 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$ 是 target 的子集。真正的逆函數 $f^\{-1\}$ 只在 $f$ 是雙射時先存在。

左逆與右逆

• 左逆 $h$ 代表 $h \circ f = id$
• 右逆 $g$ 代表 $f \circ g = id$

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

例題

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

設 $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$ 是雙射。由於 逆函數唯一，而 $h$ 已經在左邊抵消 $g$，所以 $h$ 必須就是 $g$ 的逆函數。 因此亦有 $g \circ h = id_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$ 下沒有原像。

關係

定義

關係

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

如果 $X = Y$，我們就直接叫它做 $X$ 上的關係。

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

關係是比函數更一般的概念。函數只是一種特殊關係，附帶「每個輸入剛好一個輸出」這條附加規則。

對 $R \subset X \times Y$：

• domain 是同至少一個 $y$ 有關聯的 $x$
• image / range 是被至少一個 $x$ 命中的 $y$

例題

關係未必是函數

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

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

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

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

同一個集合上的關係

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

定理

四個常用性質

一個 $X$ 上的關係可以有以下性質：

• Reflexive：每個 $x$ 都有 $xRx$
• Symmetric：$xRy$ 蘊含 $yRx$
• Antisymmetric：如果 $xRy$ 同 $yRx$，那麼就要 $x = y$
• Transitive：如果 $xRy$ 同 $yRz$，那麼就要 $xRz$

兩種特別重要的關係是：

• partial order：reflexive + antisymmetric + transitive
• equivalence relation：reflexive + symmetric + transitive

關係性質與反例

令 $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$ 相關。 因此它不是等價關係，也沒有等價類可列出。

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

symmetric 同 antisymmetric 好容易混淆，但它們意思完全不同：

• symmetric：見到單向箭咀就要兩邊都有
• antisymmetric：如果兩邊都有，那麼兩個元素就必須相等

例題

整除關係是偏序

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

這個關係是 reflexive，因為每個數都整除自己。 它是 antisymmetric，因為如果 $a \mid b$ 同 $b \mid a$，在正整數之中就有 $a = b$。 它亦是 transitive，因為整除可以沿鏈傳遞。

所以整除是 partial order。

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

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

例題

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

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

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

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

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

例題

一個簡單的等價關係

模 $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)\}$$

也就是相同餘數的整數所組成的 residue class。

等價類與商集

等價關係規定哪些差別不再區分。要把一個等價類當成新的數學對象，必須先證明：類中的不同代表元確定同一個類。下面的劃分定理使這一步精確化；整數和有理數的構造會反覆使用它。

定義

等價類

設 $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.$$

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

$0$ 元運算初看可能有些奇怪。它是沒有輸入位置、但有一個 $S$ 中輸出的函數， 所以可以理解為在 $S$ 中指定一個特別元素。

常見錯誤

常見錯誤

不要將原像與逆函數混淆

$f^\{-1\}(B)$ 永遠有意義，只要 $B$ 是 target 的子集。真正的逆函數 $f^\{-1\}$ 只在 $f$ 是雙射時先存在。

常見錯誤

對稱不等於反對稱

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

常見錯誤

關係不做函數可以有兩種錯法

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

小檢查

思考檢查

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

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

解答 · 答案

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

思考檢查

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

分清 preimage 同 inverse function。

解答 · 答案

有。原像永遠有意義。

思考檢查

如果 $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$ 是單射。

思考檢查

如果一個關係是 reflexive、symmetric、transitive，它叫甚麼？

回想會將集合分成 class 的那種關係。

解答 · 答案

它是等價關係。