2.2 函數與關係

這一單元是由集合語言通往後面幾乎所有主題的橋樑。函數、關係、以及商構造都是由同一個想法開始：先看積集，再指定哪些有序對被允許。

重點不止是認識詞語，而是要明白每個定義究竟在說明甚麼。因為後面會用同一套語言去構造 $N$ 、 $Z$ 、 $Q$ ，以及各種順序與等價類。

函數是特別的關係

定義

函數

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

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

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

$X$ 是 domain，即輸入集合。
$Y$ 是 target，即可能輸出的集合。
graph 是所有有序對 (x, y) 組成的集合。
image 是實際會出現的輸出。
preimage 是會落入某個輸出集合的輸入。

常見錯誤

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

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

常見錯誤

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$ ，所以不是函數。

解答

要記住的觀念

像、原像與合成

對 $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^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\},

因為 $A$ 之中每個元素也會落入 $B$ 。

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

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

解答

為甚麼這個區別那麼重要

單射、滿射、雙射

定義

三個常用詞

單射：不同輸入不會碰撞。
滿射：目標集合每個值也會被命中。
雙射：同時單射與滿射。

等價說法也很有用：

f 單射 iff $f(x1) = f(x2)$ 蘊含 $x1 = x2$
f 滿射 iff $f(X) = Y$
f 雙射 iff 每個目標值都剛好被命中一次

這裡之所以經常使用這幾個詞，是因為它們直接決定逆函數存不存在。

定理

逆函數存在當且僅當雙射

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

證明

為甚麼雙射會有逆

例題

單射同非單射例子

$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_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$ 。

解答

為甚麼碰撞會阻止左逆

定理

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

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

證明

證明思路

基數與運算語言

基數表示大小，但在集合論中，正確的大小比較不一定只是普通計數。兩個集合 $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$ 中指定一個特別元素。

關係

定義

關係

$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

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

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

例題

整除關係是偏序

在正整數上寫 $a \mid b$ 表示 a 整除 b。

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

所以整除是 partial order。

解答

為甚麼這個概念重要

例題

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

令 $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$ 上的等價關係。

意思是兩個整數如果有相同餘數，就屬於同一個 class。

例如模 3，整數可以分成三類：

餘 0
餘 1
餘 2

這些 classes 會分割整個集合。

等價類同商集

定義

等價類

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

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

定義

商集

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

等價類就是 quotient construction 的核心。與其逐個代表元去跟，不如直接將所有等價代表包成一個對象。

定理

等價類會分割集合

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

證明

為甚麼等價類不會部分重疊

這個就是後面用等價類構造整數同有理數的原因。

常見錯誤

不要將原像與逆函數混淆

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

常見錯誤

對稱不等於反對稱

$≤$ 是反對稱但不是對稱。等號是對稱又反對稱，而整除是反對稱但不是對稱。

常見錯誤

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

解答

答案

為甚麼這一單元重要

後面章節會不停用到這些概念：

$N$ 會透過集合語言同 induction 構造
$Z$ 同 $Q$ 會透過等價類構造
數字上的 $≤$ 是 partial order
quotient set 解釋了為甚麼同一個對象可以有許多代表元

如果這一單元清楚，後面的構造會容易許多，因為符號不再在暗中做事。

2.2 函數與關係

MATH1090：集合論

函數是特別的關係

函數

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

domain 會受語境影響

所有函數所組成的集合

把 BAB^ABA 讀成函數集合

如何仔細閱讀一個函數

平方函數會有重複輸出

要記住的觀念

像、原像與合成

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

為甚麼這個區別那麼重要

單射、滿射、雙射

三個常用詞

逆函數存在當且僅當雙射

為甚麼雙射會有逆

單射同非單射例子

先看甚麼最有效

不要將原像與逆函數混淆

左逆同右逆

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

為甚麼缺少輸出會阻止右逆

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

為甚麼碰撞會阻止左逆

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

證明思路

基數與運算語言

NNN 與 ZZZ 之間的第一個雙射

從 N×NN \times NN×N 到 NNN 的一個單射

把運算讀成函數

關係

關係

關係未必是函數

為甚麼關係語言仍然有用

同一個集合上的關係

四個常用性質

整除關係是偏序

為甚麼這個概念重要

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

一個簡單的等價關係

等價類同商集

等價類

商集

等價類會分割集合

為甚麼等價類不會部分重疊

常見錯誤

不要將原像與逆函數混淆

對稱不等於反對稱

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

小檢查

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

答案

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

答案

如果 AAA 有三個元素，而 BBB 有兩個元素，BAB^ABA 中有多少個函數？

答案

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

答案

為甚麼 F(m,n)=2m3nF(m,n)=2^m3^nF(m,n)=2m3n 定義了由 N×NN \times NN×N 到 NNN 的單射？

答案

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

答案

為甚麼這一單元重要

本節掌握 checkpoint

先備知識

本單元重點詞彙

Premium learning add-ons

本系列更多筆記

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

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

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

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

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

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

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

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

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