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。

如何小心那麼讀一個函數

例題

平方函數會有重複輸出

考慮 $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$ 同 $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。

解答

為甚麼這個概念重要

例題

一個簡單的等價關係

模 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 是雙射時先存在。

常見錯誤

對稱不等於反對稱

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

常見錯誤

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

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

小檢查

快速檢查

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

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

解答

答案

快速檢查

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

分清 preimage 同 inverse function。

解答

答案

快速檢查

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

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

解答

答案

為甚麼這一單元重要

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

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

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

MATH1090：集合論

函數是特別的關係

函數

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

domain 會受語境影響

如何小心那麼讀一個函數

平方函數會有重複輸出

要記住的觀念

像、原像與合成

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

為甚麼這個區別那麼重要

單射、滿射、雙射

三個常用詞

逆函數存在當且僅當雙射

為甚麼雙射會有逆

單射同非單射例子

先看甚麼最有效

不好將原像同逆函數混淆

左逆同右逆

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

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

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

為甚麼碰撞會阻止左逆

關係

關係

關係未必是函數

為甚麼關係語言仍然有用

同一個集合上的關係

四個常用性質

整除關係是偏序

為甚麼這個概念重要

一個簡單的等價關係

等價類同商集

等價類

商集

等價類會分割集合

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

常見錯誤

不好將原像同逆函數混淆

對稱不等於反對稱

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

小檢查

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

答案

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

答案

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

答案

為甚麼這一單元重要

先備知識

本單元重點詞彙

本系列更多筆記

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

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

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