關係（relation）

關係告訴你，對任意兩樣東西而言，它們在某種選定的意義下是否相連。「是…的手足」「小於」「和…顏色相同」——每一個都是關係，是一條規則，對每一對項目回答「是」（它們有關係）或「否」（沒有）。數學的訣竅，就是把這件事變得精確，做法很簡單：把所有算「是」的對全部列出來。

形式上，集合 A 與 B 上的二元關係 R，其實就是笛卡兒積 A × B 的一個子集：它是一個有序對的集合。我們寫 x R y，或 (x, y) ∈ R，表示「x 與 y 有關係」。對 {1, 2, 3} 上的「小於」關係而言，成立的對是 (1,2)、(1,3)、(2,3)，所以作為集合，這個關係就是 {(1,2), (1,3), (2,3)}。當 A 與 B 是同一個集合時，我們稱它為 A 上的關係，並可描述一些有用的性質：若每個元素都與自己有關係（對所有 x 有 x R x）則為自反，若 x R y 必使 y R x 則為對稱，若 x R y 與 y R z 合起來必使 x R z 則為遞移。

關係是自動機理論裡默默工作的主力。非確定型機器的轉移構成的是關係而非函數（一個輸入可以關聯到好幾個下一狀態）。圖靈機或下推自動機「計算一步」這件事，就由格局之間的一個移動關係來刻畫。而剛才提到的三個性質——自反、對稱、遞移——合起來構成這整個學科中最重要的單一關係：等價關係，這就是下一個要講的。