集合論

概述

集合論是現代數學的基礎，研究對象的集合及其運算。集合論的概念滲透到計算機科學的各個角落：從資料庫的關係模型到程式語言的類型系統，從演算法的複雜度分析到機器學習的特徵空間。

集合是一些確定且互不相同的對象（稱為元素）的整體。集合的基本性質包括：確定性、互異性、無序性。

集合運算

給定兩個集合 A 和 B：

• 聯集 A ∪ B：屬於 A 或屬於 B 的所有元素
• 交集 A ∩ B：同時屬於 A 和 B 的所有元素
• 差集 A - B：屬於 A 但不屬於 B 的元素
• 對稱差 A △ B = (A-B) ∪ (B-A)
• 笛卡爾積 A × B：所有有序對 (a,b) 組成的集合
• 冪集 𝒫(A)：A 的所有子集組成的集合，|𝒫(A)| = 2ⁿ

集合恒等式：德摩根定律 (A∪B)' = A'∩B'、(A∩B)' = A'∪B'；分配律、吸收律、冪等律等構成集合代數的基礎。

關係與函數

關係是笛卡爾積的子集 R ⊆ A × B。重要的關係性質包括：自反性、對稱性、反對稱性、傳遞性。等價關係同時滿足自反、對稱、傳遞，可將集合劃分為等價類。

函數是一種特殊的關係，每個輸入對應唯一輸出。函數可以分為單射、滿射、雙射。雙射函數（一一對應）的逆函數存在。

ZFC 公理系統

樸素集合論存在羅素悖論等邏輯困境，因此需要公理化的集合論。ZFC（Zermelo-Fraenkel + 選擇公理）是目前最廣泛使用的公理系統：

• 外延公理：兩個集合相等若且唯若它們有相同的元素
• 空集公理：存在不包含任何元素的集合
• 配對公理、聯集公理、冪集公理
• 無窮公理：承認無窮集合的存在
• 選擇公理：可以從一族非空集合中各選一個元素

相關連結

• Wiki: 集合論
• Wiki: 數論
• Wiki: 邏輯學
• 回到數學入口