第3章 關係與函數映射
3.1 從有序對到函數
A到B的關係是A×B的一個子集R。寫aRb，是說(a,b)∈R。關係可以讓同一個a連到多個b，也可以完全沒有連到。函數則要求每個a∈A恰有一個對應的b∈B。
本書把函數的定義域A、陪域B和對應規則一起保留，記作f:A→B；值域是f(A)={f(a):a∈A}，所以f(A)⊆B。相同公式配上不同論域，未必是同一個函數。本章不預設第四冊，先用有限箭頭與整數公式建立定義。
3.2 單射 滿射與雙射
單射要求不同輸入不撞到同一輸出；寫成證明形式是：若f(a₁)=f(a₂)，便有a₁=a₂。滿射要求陪域裡每個b都有至少一個原像，即存在a∈A使f(a)=b。雙射是兩種條件同時成立。
單射比較定義域內的兩個輸入；滿射要對照整個陪域，而不只對照已出現的輸出。有限圖可以逐點核對這些資格，但對無窮定義域仍需一般理由。
3.3 例題
本章有限箭頭題中寫成{a,b}的陪域，a與b用作互異的元素標籤；一般證明中的變數不因字母不同就被假設互異。
例題1 關係不一定是函數
設A={1,2}、B={a,b}。關係R={(1,a),(1,b),(2,a)}不是A到B的函數，因為輸入1有兩個不同輸出。把(1,b)拿掉，R₁={(1,a),(2,a)}才滿足每個輸入恰有一個輸出的條件。
R₁不是單射，因為1≠2卻映到同一個a；也不是到B的滿射，因為b沒有原像。若只改陪域為{a}，則滿射資格變真，但單射資格仍不變。
例題2 由等輸出證明單射
設f:ℤ→ℤ，f(n)=2n+1。若f(m)=f(n)，則2m+1=2n+1，兩邊減1再除以非零的2，得到m=n，所以f單射。
它不是到ℤ的滿射。若0有原像，就要有2n+1=0，推出n=−1/2，卻不是整數。若把陪域改為奇整數集合，任意奇整數b可寫成2k+1，取n=k便有f(n)=b，所以改後的函數是雙射。
例題3 合成要保留中間資格
設f:ℤ→ℤ，f(n)=n+1，g:ℤ→ℤ，g(n)=2n。先f後g的合成記為g∘f，其值為g(f(n))=2(n+1)=2n+2；先g後f則為f(g(n))=2n+1。
兩種合成都有資格，因為中間輸出仍在下一個函數的定義域，但兩個規則不一樣。一般而言，f:A→B、g:B→C可直接合成；若下一段只接受B的某個子集，就必須再限制能通過中間條件的輸入。
例題4 雙射的反函數
設h:ℤ→ℤ，h(n)=n−3。對每個y∈ℤ，取n=y+3便有h(n)=y，證明滿射；若m−3=n−3，則m=n，證明單射。兩項合起來保證每個y有且只有一個原像。
因此h⁻¹(y)=y+3。雙向核對：h⁻¹(h(n))=(n−3)+3=n，h(h⁻¹(y))=(y+3)−3=y。反函數是把唯一對應反過來，不是把輸出取倒數。
3.4 空定義域的邊界
從∅到任意B有一個空函數，因為沒有輸入需要違反「恰有一個輸出」。它必為單射；只有B=∅時才是滿射。若A非空，則不存在A到∅的函數，因為至少一個輸入找不到輸出。這些不是另加例外，而是原定義本身的結果。
3.5 練習
- B05-C03-Q01 判斷R={(1,a),(2,b)}是否為{1,2}到{a,b}的函數、單射與滿射。
- B05-C03-Q02 R={(1,a)}是否為{1,2}到{a,b}的函數？指出缺哪個資格。
- B05-C03-Q03 證明f:ℤ→ℤ，f(n)=n+5是雙射，並求反函數。
- B05-C03-Q04 f:ℤ→ℤ，f(n)=2n是否滿射？是否單射？
- B05-C03-Q05 令f:ℤ→ℤ，f(n)=n²，用合格見證判斷單射與滿射。
- B05-C03-Q06 設f(n)=n+2、g(n)=3n，兩者均為ℤ到ℤ，求g∘f與f∘g。
- B05-C03-Q07 若f:A→B、g:B→C均單射，證明g∘f單射。
- B05-C03-Q08 若f:A→B、g:B→C均滿射，證明g∘f滿射。
- B05-C03-Q09 描述∅→{a}與∅→∅的函數，分別判斷雙射資格。
- B05-C03-Q10 若f:A→B有g:B→A，使g∘f為A上的恆等函數，證明f單射；能否只憑這條件得到f滿射？
3.6 完整解答
Q01
每個輸入恰好出現一次，所以R是所指定的函數。兩個不同輸入映到不同的a、b，故為單射；陪域的a、b也都被命中，故為滿射。因此它是雙射，反向關係也有每個輸入唯一輸出的資格。
Q02
不是指定定義域上的函數。輸入2屬於定義域，卻完全沒有輸出；問題不是不夠單射，而是連函數的基本資格都沒有成立。若改定義域為{1}，才會得到另一個合格函數。
Q03
若m+5=n+5，則m=n，所以單射。任給y∈ℤ，取n=y−5∈ℤ，便有f(n)=y，所以滿射。反函數為f⁻¹(y)=y−5，兩種次序合成都回到各自原輸入。
Q04
若2m=2n，除以非零的2得到m=n，所以單射。它不是滿射，因為1若有整數原像n，就須n=1/2，與整數資格衝突。只需一個未命中的陪域元素，便足以推翻滿射。
Q05
不是單射：1與−1都是整數、兩者不同，平方卻都為1。也不是到ℤ的滿射：每個整數平方皆非負，所以−1沒有原像。這兩個失敗見證分別針對不同定義，不能互相代替。
Q06
(g∘f)(n)=3(n+2)=3n+6，而(f∘g)(n)=3n+2。代入n=0，兩者輸出分別為6與2，確認它們不是同一規則。合成的右邊函數先作用。
Q07
取a₁、a₂∈A並假設g(f(a₁))=g(f(a₂))。由g單射及f(a₁)、f(a₂)∈B，得到f(a₁)=f(a₂)；再由f單射得到a₁=a₂。兩次使用單射，都先核對輸入屬於正確定義域。
Q08
任取c∈C。由g滿射，存在b∈B使g(b)=c；再由f滿射，存在a∈A使f(a)=b。因此(g∘f)(a)=g(b)=c。見證先從目標c往回找，再順向代入核對。
Q09
兩者的圖都是空關係。∅→{a}雖為單射，但a沒有原像，所以非滿射、非雙射。∅→∅既無輸入碰撞，也無未命中的陪域元素，因此是雙射。不要把空函數和「不存在函數」混成同一件事。
Q10
若f(a₁)=f(a₂)，兩邊施以g，得到g(f(a₁))=g(f(a₂))；由g∘f=idₐ，便有a₁=a₂，故f單射。但滿射不保證：取A={0}、B={0,1}，f(0)=0，g(0)=g(1)=0，仍有g∘f=idₐ，可是1未被f命中。
3.7 本章回看
單射以相等輸出倒推相等輸入；滿射從任意目標構造原像。下一章把這兩種語句裡隱含的「任意」與「存在」明寫出來。