目錄
這是 Stanford CS103 導讀的第 8 篇，對應 Spring 2026 官方 Lecture 6（2026-04-13）。課程團隊是 Cynthia Bailey Lee 與 Alex Aiken；公開頁面沒有逐堂標示實際講者，因此本文不猜講者。講次頁面與完整投影片公開，錄影與逐字稿只在 Canvas／Panopto，本文沒有使用。
本講的官方題目是 Functions, Part I。它把大家早已會算的函數，重新拆成可由集合與一階邏輯檢查的物件。「是不是函數」「是不是單射」「是不是滿射」因而不再靠圖形直覺，而能轉成量詞、否定，再轉成正式證明。
1. 證明技巧表再次登場
投影片先重放證明技巧表。要證明 ∀x. A，讓讀者任取一個 x，再證明該選擇滿足 A；要證明 ∃x. A，自己提出 witness 並驗證；要證明 A → B，假設 A 後推出 B；合取分別證明兩邊，雙條件則證明兩個方向。否定題先把否定化簡，再對結果使用相應方法。
這張表不是前幾講用完即丟的工具。函數的特殊性質會用一階邏輯定義，因此證明外形早已藏在定義裡。看到全稱量詞，就知道讀者要任取元素；看到存在量詞，就知道作者要給 witness。後面每個證明都示範「先讀公式，再安排文字」。
2. 函數是確定性的對應
高中課本常把函數呈現成 f(x)=x⁴-5x²+4，程式設計則把它想成接收參數並回傳結果的程序。兩種直覺都抓到輸入與輸出，但 CS103 還要求確定性：同一輸入必須永遠得到同一輸出。因此使用隨機數的 C++ 程序雖然可以合法執行，卻不符合本講採用的數學函數定義。
確定性不是說不同輸入一定產生不同輸出。f(1)=0 與 f(2)=0 完全可能；禁止的是同一個輸入在同一函數中同時被指定兩個不相等的值。守住這條界線，稍後才不會把一般函數的要求和單射混在一起。
3. 定義域與陪域是函數身份的一部分
每個函數都帶著兩個集合：定義域是允許輸入的集合，陪域是輸出被要求落入的集合。若 f 的定義域為 A、陪域為 B，寫成 f : A → B。函數必須對 A 的每個元素都有輸出，每個輸出都屬於 B；但 B 的每個元素不一定真的被產生。
因此陪域不等於實際輸出集合。例如絕對值可宣告為 f : ℝ → ℝ。它的輸出都是實數，但負實數從未被命中。若只看公式而省略 ℝ → ℝ，便看不出未命中的負值究竟是陪域的一部分，還是根本不在討論範圍。公式相同但定義域或陪域不同，數學上可能是不同函數，也可能具有不同的單射或滿射性質。
4. 函數的兩條正式規則
投影片把 f : A → B 拆成兩條一階邏輯規則：
∀a ∈ A. ∃b ∈ B. f(a) = b
∀a₁,a₂ ∈ A. (a₁ = a₂ → f(a₁) = f(a₂))第一條說每個合法輸入都對應某個合法輸出；第二條說相等輸入必須產生相等輸出。它們也是判斷候選規則是否真為函數的檢查表。空定義域不破壞規則：沒有元素可成為反例，所以全稱敘述 vacuously true。一旦定義域有元素，每一個都要能代入並得到陪域內唯一確定的值。
第二條雖然寫了兩個變數，重點不是比較不同輸入，而是保證同一輸入不會分裂成不同答案。後面的單射會使用方向相反的 implication；現在先把「相等輸入推出相等輸出」讀準。
5. 定義函數需要三個部件
完整定義函數必須提供定義域、陪域與求值規則，三者缺一不可。圖示可用兩個橢圓表示集合，再用箭頭指定每個輸入去向；代數寫法則先寫 f : ℤ → ℤ，再寫 f(x)=x²+3x-15。前一行不是裝飾，而是交代公式能接收什麼、答案必須落在哪裡。
圖示題要逐個檢查定義域元素。若某個左側元素沒有箭頭，函數未在整個定義域上定義；若一個左側元素指向兩個不同右側元素，確定性失敗。多個左側元素指向同一右側元素仍是函數，只是未必單射。右側有元素沒被命中，也不妨礙它成為函數，只是未必滿射。
6. 分段定義的接縫要同時檢查
分段函數仍要遵守三部件契約。投影片以絕對值型規則為例：非負時回傳 n，非正時回傳 -n。因為 0 同時滿足兩個條件，必須確認兩支在 0 給出相同答案；若重疊區給出不同值，確定性就壞了。也要確認定義域中每個元素至少落入一支，否則規則不完整。
另一個 quick check 是 f(x)=(x+2)/(x+1)。宣告為 f : ℕ → ℝ 時，每個自然數輸入都有實數輸出，因此可以是函數；宣告為 f : ℝ → ℝ 時，x=-1 讓分母為零，無法在完整定義域上求值，因此不是這個型別的函數。修正方式是把定義域改成 ℝ \ {-1}，或另外一致地定義 -1 的值，而不是假裝例外不存在。
7. Involution：做兩次回到原點
若 f : A → A 且 ∀x ∈ A. f(f(x))=x，便稱 f 為 involution。定義域和陪域必須相同，因為第一次輸出的 f(x) 還要合法地送入第二次。直覺是操作自行抵消：開關翻兩次、雙重否定、-(-x)=x，以及集合的 symmetric difference (A △ B) △ B=A 都呈現這種結構。
投影片的候選包括恆等函數、取負、倒數與交換相鄰自然數的分段函數。恆等與取負是 involution。1/x 若宣告為 ℝ → ℝ，在零點甚至不是函數；改為 ℝ\{0} → ℝ\{0} 才是 involution。最後一例把偶數 n 送到 n+1、奇數送到 n-1，每對相鄰自然數彼此交換，做兩次正好回原數。
8. 用分類討論證明分段 involution
要證明交換相鄰整數的 f : ℤ → ℤ 是 involution，全稱量詞要求先任取 n ∈ ℤ，證明 f(f(n))=n。因為規則依奇偶分支，中段自然是窮盡的分類討論。
若 n 偶，f(n)=n+1，而 n+1 奇，所以第二次套用奇數分支：f(f(n))=f(n+1)=(n+1)-1=n。若 n 奇，f(n)=n-1，而 n-1 偶，所以 f(f(n))=f(n-1)=(n-1)+1=n。兩種情況涵蓋所有整數。投影片以 lemma 標記「偶數加一是奇數」與「奇數減一是偶數」；lemma 是服務主要定理的輔助定理，不是可以默默略過的跳躍。
9. 反例如何推翻 involution
證明函數不是 involution，要先否定定義：
¬∀x ∈ A. f(f(x)) = x ≡ ∃x ∈ A. f(f(x)) ≠ x.因此不必描述所有輸入，只要提出一個失敗 witness。投影片用 f : ℕ → ℕ, f(n)=n²：取 n=2，有 f(f(2))=f(4)=16≠2。這個短證明的力量來自量詞完全對準，而不是計算複雜。
反例也提醒我們不能用幾個成功樣本證明全稱命題。0 與 1 的確反覆平方後不變，但這只能說兩個點通過，無法推出所有自然數都通過。證明 involution 必須從任意輸入推導；否定它，一個經驗證的失敗輸入就夠。
10. 單射的兩個等價讀法
函數 f : A → B 是 injective（one-to-one），意思是不同輸入產生不同輸出：
∀x₁,x₂ ∈ A. (x₁ ≠ x₂ → f(x₁) ≠ f(x₂)).其逆否命題是常用等價形式：∀x₁,x₂ ∈ A. (f(x₁)=f(x₂) → x₁=x₂)。第二式常比較好算，因為可以從兩個函數值相等直接代數消去。注意它比一般函數的確定性更強：函數規則說「輸入相等則輸出相等」；單射把可推理方向反過來，說「輸出相等則輸入相等」。交換這兩句，是本講最常見的定義錯誤之一。
11. 證明線性函數是單射
令 f : ℕ → ℕ、f(n)=2n+7。任取 x₁,x₂ ∈ ℕ 並假設 f(x₁)=f(x₂)。依定義展開得 2x₁+7=2x₂+7，兩側減七再除以二，得到 x₁=x₂。這正好完成等值輸出版本的 implication。
寫作時應明說任取兩個定義域元素、假設 antecedent、最後指出 consequent 已成立。正文不需要塞入 ∀ 與 → 符號；形式式用來設計證明，成品仍以清楚文字呈現。若硬走「輸入不同推出輸出不同」也能成功，但常需處理不等式或反證，等值版本在代數函數上通常更直接。
12. 否定單射就是找 collision
令 f : ℤ → ℕ、f(x)=x⁴。單射定義的否定是：存在 x₁,x₂ ∈ ℤ，兩者不同但函數值相等。選 x₁=1、x₂=-1，有 1≠-1，卻有 f(1)=1=f(-1)，便完成反例。
這種不同輸入撞到同一輸出的現象叫 collision。證明「不是單射」必須同時驗證兩件事：witness 確實不同，輸出確實相同。只展示 f(1)=f(-1) 而未說明輸入不同，形式上少了一半；只展示不同輸入，卻沒有相等輸出，也沒有觸及單射的否定。
13. 滿射要求陪域每點都有原像
函數 f : A → B 是 surjective（onto），若 ∀b ∈ B. ∃a ∈ A. f(a)=b，也就是陪域每個目標都有至少一個原像。量詞順序很重要：先由讀者任取目標 b，作者才依這個 b 建構輸入 a。若改成先找一個固定 a 再覆蓋所有 b，就要求單一輸入同時產生所有輸出，是完全不同而通常不可能的命題。
滿射高度依賴陪域。f(n)=2n 若從自然數到自然數，所有奇數都漏掉；若把陪域改成偶自然數集合，它便可能滿射。圖示上，滿射要求右側每點至少收到一支箭頭；左側多個元素可以指向同一點，所以滿射不自動代表單射。
14. 滿射與非滿射的 witness 策略
令 f : ℝ → ℝ、f(x)=2x。任取目標 y ∈ ℝ，選 x=y/2。這個 x 是合法實數，而且 f(x)=2(y/2)=y，所以每個陪域元素都有原像。滿射證明的核心不是「看起來都有」，而是提供能依任意目標產生合法輸入的公式。
再看 g : ℕ → ℕ、g(n)=2n。否定滿射定義得到 ∃b ∈ ℕ. ∀a ∈ ℕ. g(a)≠b。投影片選 b=137。任取 a ∈ ℕ，g(a)=2a 為偶數，而 137 為奇數，因此永不相等。先找一個陪域漏點，再證明所有定義域輸入都無法命中，正好對應「存在—全稱」順序。
15. 從定義直接生成證明流程
本講三類性質可濃縮成流程。證明 involution：任取輸入，計算兩次並證明回原點；否定它：找一個回不去的輸入。證明 injective：任取兩輸入，假設輸出相等後推出輸入相等；否定它：找一組 collision。證明 surjective：任取陪域目標，依目標建構原像；否定它：找一個漏掉的目標，再證明沒有任何輸入能命中。
每次動筆前做四步自查：寫出完整型別 A → B；抄出性質的量詞定義；若題目是否定，先把否定推到原子敘述；最後按最外層量詞決定誰選物件。這套方法把「不知道怎麼起手」改造成機械但可靠的 proof planning，也把先前邏輯單元和後續函數單元接在一起。
16. 常見錯誤與自我練習
常見錯誤包括：只寫公式不寫定義域與陪域；把陪域誤當實際輸出集合；漏查分段規則的空隙與重疊；把確定性誤寫成單射；證明滿射時先固定一個與目標無關的輸入；用有限幾個成功樣本證明全稱命題；把形式邏輯原封不動塞進證明，卻沒有翻成可讀推理。
可以用四題檢查自己。第一，判斷 x ↦ 1/x 在 ℝ → ℝ 與 ℝ\{0} → ℝ\{0} 的差異。第二，證明 x ↦ x+5 在 ℤ → ℤ 同時單射且滿射。第三，找出 x ↦ x² 在 ℤ → ℕ 不是單射的 collision，並思考它是否滿射。第四，設計有限集合上的 involution，畫箭頭後用 f(f(x))=x 逐點驗證。每題都先寫量詞，再寫 prose proof；若兩者選擇順序不一致，先回頭找問題。
材料缺口與閱讀界線
完整投影片足以核對函數正式規則、定義方式、分段函數、involution、單射、滿射及五個主要證明例子，因此本文依 deck 重建 agenda。投影片不是錄影，不保存所有口頭轉折、學生問題或臨場補充；本文不把作者銜接包裝成講師原話，也未使用受限的作業解答。
更新紀錄
- 2026-08-22：從官方 Functions, Part I 完整投影片逐節重建正文、metadata、證明例子與材料界線。
參考資料
Loading...