集合運算與冪集

集合 (set) 是數學的基本容器。運算:聯集 $A\cup B$、交集 $A\cap B$、差集 $A\setminus B$(在 $A$ 不在 $B$)、對稱差 $A\triangle B$(只在其中一個)、補集 $A^c$。計數公式 $|A\cup B| = |A|+|B|-|A\cap B|$。

冪集 (power set) $\mathcal{P}(A)$ 是 $A$ 的所有子集合所成的集合,$|\mathcal{P}(A)| = 2^{|A|}$(每個元素選或不選)。笛卡兒積 $A\times B$ 是所有有序對,$|A\times B| = |A||B|$;$A$ 到 $B$ 的函數有 $|B|^{|A|}$ 個;$A$ 上的二元關係是 $A\times A$ 的子集合,共 $2^{|A|^2}$ 個。

算例:$A = \{1,2,3\}$,$\mathcal{P}(A)$ 有 8 個元素,包含 $\emptyset$ 與 $A$ 自己。

集合語言統一了機率(事件)、資料庫(關聯表就是笛卡兒積的子集)、邏輯(集合運算對應 $\lor$、$\land$、$\lnot$);Cantor 用冪集證明無窮有不同大小。