冪集（power set）
集合 A 的冪集是 A 所有子集構成的集合——也就是從它的元素中挑出零個或多個的每一種可能方式。想像你有一個小衣櫃，把所有可能的穿搭都列出來，包括「這個衣櫃裡什麼都不穿」這個選擇，以及「全部都穿上」這個選擇：這份完整的選擇目錄就是冪集。它是一個成員本身就是集合的集合，乍看奇怪，但其實再正常不過。
我們把 A 的冪集寫成 P(A) 或 2^A。若 A = {a, b}，則 P(A) = {∅, {a}, {b}, {a, b}}：空選擇、兩個單元素選擇，以及整體。一個漂亮的計數事實解釋了 2^A 這個寫法：對 n 個元素中的每一個，你都獨立地做一次「要不要納入」的是非選擇，於是總共有 2 × 2 × … × 2 = 2^n 個子集。所以 3 個元素的集合有 2^3 = 8 個子集，而即使只有 10 個元素的集合，子集也已經高達 1024 個。
冪集是這整個學科中最重要的構造之一背後的祕密：把非確定型有限自動機（NFA）轉成確定型。因為 NFA 可以「同時處於好幾個狀態」，模擬它的 DFA 必須追蹤 NFA 此刻處於活躍的是哪一個狀態子集——所以 DFA 的狀態恰好就是 NFA 狀態集合的冪集成員。這也是為什麼這個轉換可能造成指數爆炸：n 個 NFA 狀態原則上可以產生多達 2^n 個 DFA 狀態。
P({1, 2, 3}) 有 2^3 = 8 個成員：∅、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2,3}。注意空集合 ∅ 與整個集合 {1,2,3} 永遠都是冪集的成員。
一個 3 元素集合有 8 個子集，其中兩個是空集合與整個集合。
別把元素和單元素子集搞混：a ∈ A 與 {a} ⊆ A 是兩個不同的陳述。P(A) 的成員都是集合，所以 {a} ∈ P(A)，但 a ∉ P(A)。