§1-3  補集、De Morgan 與笛卡兒積

「屬於 A 但不屬於 B」的元素合起來是什麼集合?對交集與聯集取補集,等式為什麼會左右互換?又要怎麼從兩個集合造出平面上的點集?

集合的減法

朋友對花生過敏,你替他看菜單。這時你關心的不是整份菜單,也不是含花生的黑名單,而是「菜單上、扣掉黑名單」剩下的部分——能點的那一頁。日常語言裡這叫「排除」;集合的語言裡,這是第三種基本運算:從一個集合裡減去另一個。

交集是「且」、聯集是「或」,現在補上「但不」。三個湊齊之後,本篇馬上兌現兩張支票:一條把集合切成不重不漏兩塊的定理,以及一條讓「排除」與交聯互動的漂亮定律。

1.6  DEFINITION
The complement of B relative to A, written A∖B and read “A minus B,” is the set of all those elements of A that do not belong to B.
When the ambient set A is understood from context, we write 𝒞(B) and speak simply of the complement of B.
B 相對於 A 的 complement(補集)A∖B,收「屬於 A 但不屬於 B」的一切元素:A∖B = {x ∈ A : x ∉ B}。全域集合 A 有默契、不必每次明說時,簡寫 𝒞(B)。
正例:{1, 2, 3, 4}∖{3, 4, 5} = {1, 2}——3 與 4 被扣掉,5 本來就不在菜單上,扣不扣無感。反例(減法不能對調):{3, 4, 5}∖{1, 2, 3, 4} = {5} ≠ {1, 2}——兩個方向剩下的東西完全不同。
A B A∖B 黃色月牙=留在 A、又躲開 B 的元素

這張圖在畫定義 1.6 收哪塊區域:從 A(實線圓)中挖掉與 B(虛線圓)重疊的部分,剩下的黃色月牙就是 A∖B。重疊區被扣掉、B 自己獨有的區域則從頭到尾與 A∖B 無關。

回頭看 §1-1 那張四種處境的圖:處境 (1) 的元素住在 A ∩ B,處境 (2) 的元素住在 A∖B。而「屬於 A」的元素恰好就是處境 (1) 加處境 (2)——這個觀察值得升格成定理:

1.7  THEOREM
For any sets A and B, the sets A ∩ B and A∖B are disjoint, and A = (A ∩ B) ∪ (A∖B).
拿 B 當刀,A 被切成兩塊:留在 B 裡的 A ∩ B,與躲開 B 的 A∖B。兩塊不重(disjoint)、合起來不漏(聯集恰是 A)。
正例:A = {1, 2, 3, 4}、B = {3, 4, 5}:兩塊分別是 {3, 4} 與 {1, 2},果然不重不漏拼回 A。正例(極端情形也成立):A 與 B disjoint 時,兩塊是 ∅ 與 A 整個——定理照樣成立,只是刀沒切到肉。
PROOF

設 A、B 為任意集合,要證兩件事:兩塊不相交;兩塊拼回 A。

證明計畫 · 由所求想起
要證(一):A ∩ B 與 A∖B 無共同元素。
⇢ 證「不存在」走反證:共同元素得同時通過「屬於 B」與「不屬於 B」兩關——§1-1 的紀律說恰居其一,矛盾現成。
要證(二):聯集恰是 A。
⇢ 相等即雙向包含(定義 1.1)。方向一:A 的元素依「在不在 B」二選一入塊;方向二:兩塊的定義裡本來就寫著「屬於 A」,定義自帶。
Proof.  First, disjointness. Suppose some x were in both A ∩ B and A∖B. Because x ∈ A∖B demands x ∉ B, while x ∈ A ∩ B demands x ∈ B, the element x would satisfy both x ∈ B and x ∉ B — impossible. Hence the two sets share no element.
先證不重。假設真有元素 x 同時住在兩塊裡,那麼依定義,x ∈ A∖B 要求 x ∉ B,而 x ∈ A ∩ B 要求 x ∈ B——兩個要求互相矛盾。因為 §1-1 開頭立過紀律(x ∈ B 與 x ∉ B 恰有一個成立),這樣的元素不存在,所以兩塊不相交。
Next, take any x ∈ A. Either x ∈ B, and then x ∈ A ∩ B; or x ∉ B, and then x ∈ A∖B. Therefore A ⊆ (A ∩ B) ∪ (A∖B).
再證不漏。任取 A 的元素 x,問它屬不屬於 B——由於答案恰有一個,x 必被分進兩塊之一:因為 x ∈ B 時 x 同時屬於 A 與 B、也就是 x ∈ A ∩ B;而 x ∉ B 時依定義 x ∈ A∖B。於是 A 的每一個元素都屬於兩塊的聯集,第一個包含方向成立。
Conversely, every element of A ∩ B lies in A, and so does every element of A∖B. Hence (A ∩ B) ∪ (A∖B) ⊆ A, and the two inclusions give A = (A ∩ B) ∪ (A∖B).
反方向不需要新論證:依定義,A ∩ B 的每個元素都屬於 A,A∖B 的每個元素也都屬於 A,所以兩塊的聯集包含於 A。兩個方向的包含都成立,由 定義 1.1,兩集合相等。
A 被切成不重不漏的兩塊:A = (A ∩ B) ∪ (A∖B)。∎
A B A∖B A∩B 黃月牙+藍透鏡=整個 A,兩塊無重疊

這張圖在畫定理 1.7 的那一刀:B(虛線)把 A 切成藍色透鏡(A ∩ B)與黃色月牙(A∖B)。兩塊顏色互不重疊(disjoint),拼起來恰好填滿 A 的圓。

最後一條恆等式回答這個問題:「排除」碰上交與聯,會發生什麼事?答案漂亮到配得上一個專名。

1.8  THEOREM · De Morgan Laws
For any sets A, B, C:
A∖(B ∪ C) = (A∖B) ∩ (A∖C),
A∖(B ∩ C) = (A∖B) ∪ (A∖C)。
從 A 裡排除「B 或 C」,等於「排除 B」且「排除 C」;排除「B 且 C」,等於「排除 B」或「排除 C」。一句話:減號穿過括號時,∪ 與 ∩ 互換。
正例(驗第一式):A = {1, 2, 3, 4}、B = {2, 3}、C = {3, 4}。左邊:B ∪ C = {2, 3, 4},排除後剩 {1}。右邊:A∖B = {1, 4}、A∖C = {1, 2},交集 {1}。吻合。反例(∪ 不換成 ∩ 就錯):同組集合下 (A∖B) ∪ (A∖C) = {1, 2, 4} ≠ {1}——減號穿過括號卻不翻轉運算,等式立刻破功。
PROOF

證第一式 A∖(B ∪ C) = (A∖B) ∩ (A∖C);第二式的證法只差一個對調,末尾交代。

證明計畫 · 由所求想起
要證:兩集合相等。⇢ 依 定義 1.1(雙向包含)。
⇢ 關鍵翻譯只有一句:「不屬於 B ∪ C」=「不屬於 B、且不屬於 C」——躲開一場聯集,就得同時躲開它的每個成員。
Proof.  Take any x ∈ A∖(B ∪ C). Then x ∈ A while x ∉ B ∪ C. Because landing in B or in C would already place x inside B ∪ C, the element x belongs to neither. So x ∈ A with x ∉ B — that is, x ∈ A∖B — and likewise x ∈ A∖C. Hence x ∈ (A∖B) ∩ (A∖C).
先走第一個包含方向。任取左邊的元素 x:它屬於 A,且不屬於 B ∪ C。這裡用計畫裡的那句翻譯——因為屬於 B 或屬於 C 都會使 x 屬於聯集,而 x 不屬於聯集,所以 x 既不屬於 B、也不屬於 C。於是 x 同時滿足「屬於 A 且不屬於 B」與「屬於 A 且不屬於 C」,也就是同時屬於 A∖B 與 A∖C,因此屬於右邊的交集。拿定理卡 inst 的數字對照:x = 1 不屬於 {2, 3, 4},它確實也各自不屬於 {2, 3} 與 {3, 4}。
Conversely, take any x ∈ (A∖B) ∩ (A∖C). Then x ∈ A, with x ∉ B and x ∉ C. Since x avoids both B and C, it avoids their union, so x ∈ A∖(B ∪ C).
第二個方向反著用同一句翻譯:因為 x 不屬於 B 也不屬於 C,而聯集的每個元素必屬於 B、C 之一,所以 x 不屬於 B ∪ C。再加上 x ∈ A,依定義 1.6,x 屬於左邊的 A∖(B ∪ C)。
The two inclusions give the first law by Definition 1.1. For the second law, run the same trace with the roles of ∪ and ∩ exchanged throughout.
兩個方向的包含都成立,由 定義 1.1,第一式得證。第二式不必重新發明:把追蹤過程裡每個「或」換成「且」、「且」換成「或」,逐行照走一遍,就是它的完整證明。
減號穿過括號,∪ 與 ∩ 互換——De Morgan 定律成立。∎
A B C 兩邊都躲開

這張圖在畫 De Morgan 第一式的兩份收據指向同一塊黃色:把 B ∪ C 一次挖掉(左式),與先各自挖掉 B、再挖掉 C(右式的交集),剩下的都是這塊月牙。

三種運算、三條定理全數到手。往下是本節最後一個新念頭——維度。喝口水,馬上回來。

有序對與平面

套餐是「一份主餐配一杯飲料」。菜單上有三種主餐、兩種飲料,套餐就有六種——而且「牛肉麵配紅茶」跟「紅茶配牛肉麵」是同一份套餐嗎?不是的話,順序就有意義。到目前為止集合都是不認順序的({1, 2} = {2, 1}),要談「先誰後誰」,需要一個新造物:

1.9  DEFINITION
For two non-empty sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) whose first entry a comes from A and whose second entry b comes from B.
非空集合 A 與 B 的 Cartesian product(笛卡兒積)A × B,收所有「第一分量取自 A、第二分量取自 B」的有序對 (a, b)。有序對的全部要點就一條:(a, b) = (a′, b′) 恰於 a = a′ 且 b = b′。
正例:(2, 5) ∈ {1, 2, 3} × {4, 5}——第一分量 2 來自第一個集合、第二分量 5 來自第二個。反例:(5, 2) ∉ {1, 2, 3} × {4, 5}——分量對調就出局,「有序」是玩真的。
有序對不是二元集合:{1, 2} = {2, 1},但 (1, 2) ≠ (2, 1)。花括號只認成員,圓括號還認位置。順帶一提,有序對其實可以完全用集合造出來——把 (a, b) 定義成 {{a}, {a, b}} 就能推出上面的相等判準——不過本讀本用到的只有判準本身,造法當成趣聞即可。
例 2畫出 {1, 2, 3} × {4, 5},再畫出 A = {x ∈ ℝ : 1 ≤ x ≤ 2} 與 B = {x ∈ ℝ : 0 ≤ x ≤ 1 或 2 ≤ x ≤ 3} 的乘積
笛卡兒積最好的理解方式是把它畫在平面上——順便打破「乘積 = 矩形」的錯覺,這個錯覺在之後畫 ℝᵖ 的圖時會誤事。
把兩個乘積的元素在平面上標出來,並描述形狀。
  1. {1, 2, 3} × {4, 5}:第一分量三選一、第二分量二選一,共 3 × 2 = 6 個有序對——(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)。畫在平面上是整齊的格點陣:橫向三個位置對應 A 的三個元素,縱向兩個位置對應 B 的兩個元素。
  2. 第二個乘積:第一分量在橫軸的區間 [1, 2] 掃動,第二分量在縱軸的 兩段 區間掃動。因為 B 斷成兩段,乘積跟著斷成上下兩個矩形——不是一整塊。
  3. 形狀的規律:固定第二分量、沿水平方向切一刀,切面若非空就是整個 A 的複本;固定第一分量、沿垂直方向切一刀,切面若非空就是整個 B 的複本(右圖在高度 1 到 2 之間水平切下去是空的——那段高度不屬於 B)。A、B 都是整段區間時乘積才是單一矩形;因子一斷,乘積就跟著碎。
123 45 六個格點 12 0123 B 斷兩段,乘積斷兩塊

這張圖在畫例題的兩個答案:左邊 {1, 2, 3} × {4, 5} 是六個格點;右邊因為 B 斷成 [0, 1] 與 [2, 3] 兩段,乘積成了上下兩個藍色矩形,中間整條帶狀是空的。

乘積的形狀由兩個因子共同決定,矩形只是「兩個因子都是整段」時的特例。日後看到 ℝ × ℝ 記得它的本體:全體有序實數對——這正是平面座標的數學身分。
—— 第三階段到此結束 ——

本節收官:且、或、但不三種運算齊備,1.7 把集合切成不重不漏兩塊,De Morgan 讓減號穿過括號時交聯互換,笛卡兒積則替「順序」與「維度」開了門。整個 §1 走完了,值得起身好好休息——出去走一圈,回來再開下一節。臨走前一則家規:「不准(打電動 ∪ 熬夜)」,經 De Morgan 展開等於「不准打電動 ∩ 不准熬夜」——沒有漏洞可鑽。

下一幕預告

集合會靜靜待著,數學要動起來。下一節的主角是函數——在兩個集合之間搭起對應的機制。你會發現函數本身也是一個集合(而且就住在本篇剛蓋好的笛卡兒積裡),「定義域」「值域」「反函數」這些詞會第一次獲得嚴格的身分。