集合（set）

集合（set）就是一堆東西湊在一起，不能重複、也不講順序——就像一個裝著各不相同物品的袋子，唯一重要的事情是某樣東西在不在裡面。可以想成派對的賓客名單：問題從來不是某個名字寫了幾次、或先後寫在哪裡，而只是每個人在不在名單上。在計算理論裡幾乎所有東西都是集合：字母表是符號的集合，語言是字串的集合，有限自動機（finite automaton）有一個狀態的集合。

我們把集合的成員列在大括號裡來表示，例如 {a, b, c}，或用一條規則來描述，例如 {n : n 是偶數}，讀作「所有使得 n 是偶數的 n 構成的集合」。最基本的提問是「成員資格」：我們寫 x ∈ S（讀作「x 是 S 的元素」，∈ 是屬於符號）表示 x 在集合 S 裡，寫 x ∉ S 表示不在。有一個特殊的集合，空集合 ∅（寫成 {} 或用符號 ∅），完全沒有成員；它不是「什麼都沒有」，而是一個確實存在、只是恰好空著的集合，就像空袋子仍然是一個袋子。當 A 的每個元素都在 B 裡時，我們說 A 是 B 的子集，寫作 A ⊆ B（⊆ 是子集符號）。

集合之所以重要，是因為它讓我們能夠對含糊的概念說得一清二楚。後面當我們說「某個確定型有限自動機接受語言 L」時，意思是 L 是一個特定的字串集合，而機器的工作就是針對每一個可能的輸入回答「這個字串在不在 L 裡？」這個成員問題。兩個集合相等，恰好是當它們擁有完全相同的成員——所以 {a, b} 和 {b, a, a} 是同一個集合，因為順序和重複都不算數。