動機
假設程式為每條記錄指定一個類別。先篩選記錄再收集類別,與先收集類別再篩選標籤,並不是同一種操作。多條記錄可能屬於同一類別,聲明過的某些類別也可能從未出現。這兩點解釋了許多涉及函數的集合公式為甚麼失效。
本節補充計數與算法規格所需的集合和函數基礎。我們把集合恆等式讀成成員條件,跟蹤映射的定義域、陪域,並區分把條件拉回輸入與把集合送往輸出。
定義
定義 12.4.1
(集合、子集與集合運算)
表示 是集合 的成員。 表示 的每個成員都屬於 ;相等需要兩個方向的包含。空集 沒有成員,所以它是任何集合的子集。但 表示空集本身是 中的一個對象,不能由子集關係推出。集合 有一個成員,並非空集。
取補集前先固定全集 。對 ,並集表示「至少屬於一個」,交集表示「同時屬於兩個」,差集 表示「屬於 而不屬於 」。 的補集是 。冪集 由 的全部子集組成,包括空集和 自身。笛卡兒(Descartes)積 由滿足 的有序對 組成;交換座標通常改變對象。
定義 12.4.2
(函數、定義域與陪域)
函數 為定義域 中的每個輸入指定陪域 中恰好一個輸出。它的圖是 的子集 。漏掉某個輸入,或讓同一輸入對應兩個不同輸出的關係,都不是以 為定義域的函數圖;不同輸入則可以共享輸出。
定義 12.4.3
(像、原像與纖維)
對 和 ,定義
它們分別是 的像和 的原像。前者是 的子集,後者是 的子集。每個函數都有原像運算,即使沒有逆函數。輸出 的纖維是 ,可以為空,也可以含多個輸入。
定義 12.4.4
(複合、單射與滿射)
若 ,複合 定義為 ,即先用右邊的映射。恆等映射 把每個元素送到自身。單射要求相等輸出只能來自相等輸入,滿射要求 ,雙射同時滿足兩者。下文構造逆映射時集合均為有限集;集合恆等式本身不依賴有限性。
定理/命題
定理 12.4.5
(原像保持集合運算)
對 和 ,有
此外,,。對 和 ,
定理 12.4.6
(像與往返運算)
對 和 ,有
交集包含式對所有 都成為等式,當且僅當 單射。同樣, 對所有 成立,當且僅當 單射。最後一式對所有 都等於 ,當且僅當 滿射。
定理 12.4.7
(有限集上的逆映射與空集邊界)
設 是有限集之間的函數。左逆是滿足 的映射 ;它存在,當且僅當 單射,並且 與 至少一項成立。右逆是滿足 的映射 ;它存在,當且僅當 滿射。雙側逆存在,當且僅當 雙射,此時逆唯一。
證明思路
先翻譯成員條件
證明
(藉成員條件證明原像公式)
任取 。它屬於並集的原像,表示 ,即 或 ,恰好是屬於右邊並集的條件。把「或」換成「且」即得交集公式。由於 總屬於 , 就是在全集 內有 ,得到補集公式。空集與全集的原像也直接由定義得到。複合公式則逐步寫成
每步都考察同一個輸入,沒有使用逆函數。
概念視角算法
原像就是輸入篩選
對有限編號集合,用輸出下標表保存函數,用成員位元陣列保存子集。求原像時,遍歷輸入並讀取其輸出下標處的成員位元。當下標和表項都能放入機器字時,這需要 次字操作。若從輸入成員陣列構造像,先清空輸出陣列,再遍歷輸入並標記被選輸入的輸出,需要 次操作。重複標記不產生重複集合成員。這說明拉回條件無需搜尋逆函數,也說明像為何丟失了共享輸出的輸入數量。
證明
(像、見證與交集包含式)
對像的並集公式,輸出 在 中有原像,恰好表示它至少在 之一中有原像。若原像屬於 ,它同時屬於兩者,得到 。
設 單射,且 。則 ,其中 ;單射給出 ,故 。反過來,若 不單射,取 使 。令 ,則 ,而 ,等式不成立。
證明透視
一個共同見證與兩個分別存在的見證
包含方向只需要一個見證,而這個見證本來就同時屬於兩個集合。反向包含才是證明性質改變之處:屬於 只給出兩個輸入 與 ,它們共享一個輸出;屬於 卻需要一個同時屬於兩集合的輸入。因此關鍵的一步是由兩個見證合成一個見證,單射正好在此處使用,用來確認 。這個假設不能減弱:任何碰撞 ()都會給出不相交的單點集,使等式失效。這段論證沒有用到滿射;只要找到同時屬於兩集合的輸入,證明就完成。
往返時丟失了甚麼
證明
(往返運算補入與刪去的內容)
若 ,則其輸出屬於 ,因此 。後者還包含與 中某個輸入共享輸出的全部輸入。單射時沒有額外輸入;反之,若所有這樣的往返都保持 ,取 ,任何滿足 的 都只能等於 ,故函數單射。
一個輸出屬於 ,恰好表示它屬於 且確實有輸入,所以該集合等於 ,不需要滿射。滿射時它對所有 都等於 ;反之取 就得到 。若只對某一個 成立,僅說明該集合的所有輸出都出現過,不能推出對整個陪域滿射。
親自構造逆映射
證明
(逆映射的存在條件)
若 ,對等式 應用 就得 。此外,非空 到空 的函數不存在。這給出左逆的兩個必要條件。反過來,若 單射且 非空,選 ;對 令 為其唯一輸入,對其他 令 ,就有 。若 為空,已有函數 的存在迫使 也為空,空映射滿足要求。
若 ,每個 都有輸入 ,故 滿射。反過來,把有限集 的元素逐個列出,為每個元素選一個輸入,就構成右逆; 為空時用空映射。雙射的每個輸出恰有一個輸入,因而該構造給出雙側逆,且逆只能把輸出送回這個唯一輸入,所以唯一。雙側逆也必然使 同時單射和滿射。更一般地,若左逆 和右逆 同時存在,則 。
例題詳解
例題 12.4.8
(既有碰撞又有未使用輸出的分類映射)
設 ,,且 ,。取 ,它們的交集為空,所以 ,而 。對 先取像再取原像,得到 。對 ,先取原像得 ,再取像只剩 :綠色從未出現。這展示了兩種不同的資訊損失。
例題 12.4.9
(在固定全集內證明集合恆等式)
對 ,證明 。任取 ,屬於左邊當且僅當既不屬於 也不屬於 ,恰好是同時屬於兩個補集。若 ,兩邊都是 。若中途改在 自身內取 的補集,得到空集,卻已經改變了問題。
例題 12.4.10
(沿複合映射拉回篩選條件)
設 ,, 返回輸入除以二的餘數。映射 為兩個餘數命名。複合標籤為奇數的輸入是 。分步拉回時,先得 ,再得 。雖然 不單射,原像公式仍完全成立。
例題 12.4.11
(左右逆承擔不同義務)
包含映射 有左逆 ,卻沒有右逆,因為輸出 沒有輸入。映射 有右逆 ,卻沒有左逆,因為同一輸出無法同時恢復兩個不同輸入。最後,唯一的映射 單射卻沒有左逆:左逆應是從 到空集的映射,而這樣的映射不存在。
常見錯誤
常見錯誤
(把原像與原函數直接約去)
不能把 與 當作形式符號直接約去。像的原像會補進整個纖維,原像的像會刪掉從未出現的輸出。雙射的逆函數作用於元素,原像運算作用於子集;即使兩者有聯繫,也不能忽視對象類型。
反例模式
像不一定保持補集
直觀上容易猜測 。在分類映射中取 ,則 ,但 。紅色出現在左邊,是因為 與 碰撞;綠色出現在右邊,是因為沒有記錄帶有這個標籤,所以兩邊的失效方向並不相同。普遍成立的是原像的補集公式 ,輸出側全集為 ,輸入側為 。
常見錯誤
(把單向包含當作等式)
證明 或 只得到一個界,並沒有證明等式。反向包含是另一個命題;如上面的證明所示,它對所有集合成立,恰好需要單射或滿射的假設。
常見錯誤
(把左逆與右逆的作用次序弄反)
複合前先標出每個映射的類型。左逆 在 中作用於 之後,右逆 在 中作用於 之前。空集要用這些類型檢驗,不能當作記號問題略過:空映射 單射,卻沒有左逆。
總結
集合恆等式來自等價的成員條件。原像把條件拉回同一個輸入,因而保持並、交與補。像需要存在見證,碰撞使兩個見證未必相同,缺失輸出又限制了往返恢復。單射與滿射刻畫這些資訊能否恢復,有限逆映射的構造則明確了存在性與空集條件。
練習
快速檢查
(逐元素證明 。判斷 與 是否成立。)
解答 · 答案
屬於左邊等價於屬於 而既不屬於 也不屬於 ,即同時屬於 和 。空集唯一的子集是空集,故 ;成員斷言為真,與空集相等的斷言為假。
快速檢查
(對任意 和 ,證明 。給出嚴格包含的例子,並證明單射時成為等式。)
解答 · 答案
若 ,選 使 。該 不屬於 ,否則 ,所以 。分類映射中取 ,左邊為空,右邊為 。單射時若 且 ,則 中不可能另有輸入得到 ,給出反向包含。
快速檢查
(證明對某個固定 , 當且僅當 是若干完整非空纖維的並。包括 的情況。)
解答 · 答案
像的原像補入與 中某個元素共享輸出的全部輸入。若沒有補入新元素,每個這樣的完整纖維都已包含在 中,故 是這些纖維的並。反過來,纖維的並已包含所有共享輸出的輸入,往返便不會擴大它。空集是空族纖維的並,也滿足等式。
快速檢查
(有限集 大小分別為 。對給定單射 ,若 ,求左逆數量。對給定滿射,用纖維大小表示右逆數量。另行解釋空雙射。)
解答 · 答案
在 的 個輸出上,左逆已被迫確定;其餘 個輸出各有 種取值,故有 個左逆。滿射的每個 必須從非空纖維中選取,故右逆數為 。空雙射恰有一個逆,即空映射,與空積為一相符。左逆計數限定 ,是為了無需借助 的約定。