跳转至

Lecture 1 集合论

一、 集合的基本概念

1. 核心定义与性质

  • 两大核心性质：
    • 互异性：集合中的元素是彼此不同的，例如 \(\{1, 2, 3, 3, 3\} = \{1, 2, 3\}\) 。
    • 无序性：集合的元素是没有排列顺序的，例如 \(\{1, 2, 3\} = \{3, 2, 1\}\) 。
  • 属于关系：元素与集合之间只有“属于”(\(\in\)) 和“不属于”(\(\notin\)) 两种关系。
    • 易错点：规定任何集合 \(A\) 都有 \(A \notin A\)。

2. 集合的两种表示方法

  • 列举法：直接列出所有元素，例如三原色集合 \(A = \{红, 绿, 蓝\}\) 。
  • 描述法：提取公共属性，例如 \(B = \{x | x \in \mathbb{R}, x^2 - 1 = 0\}\) 。

二、 集合之间的关系

1. 包含与相等

  • 子集 (Subset)：如果 \(B\) 中的每一个元素都在 \(A\) 中，则 \(B\) 是 \(A\) 的子集，记作 \(B \subseteq A\) 。形式化描述：对任意 \(x\)，若 \(x \in B\)，则 \(x \in A\)。
  • 相等 (Equality)：\(A = B\) 当且仅当 \(A \subseteq B\) 且 \(B \subseteq A\) 。这是证明两个集合相等最常用的标准套路。
  • 真子集 (Proper Subset)：\(B \subseteq A\) 且 \(B \neq A\)，记作 \(B \subset A\) 。

2. 特殊集合

  • 空集 (\(\emptyset\))：不含任何元素的集合 。
    • 空集是一切集合的子集 。
    • 空集是唯一的 。
    • \(\emptyset \in \{\emptyset\}\) 是正确的，因为前者是后者的元素。
    • \(\emptyset \subseteq \{\emptyset\}\) 也是正确的，因为“空集是一切集合的子集”。
  • 幂集 (Power Set)：由集合 \(A\) 的全体子集构成的集合，记作 \(P(A)\)。
    • 考点：如果 \(A\) 有 \(n\) 个元素，那么它的幂集 \(P(A)\) 包含 \(2^n\) 个元素 。求幂集时千万别漏掉空集 \(\emptyset\) 和集合本身 \(A\) 。
  • 全集 (\(E\))：在一个具体问题中，所有涉及的集合都是它的子集 。

三、 集合的基本运算

1. 四大基本二元运算

  • 并集 (Union)：\(A \cup B = \{x | x \in A \vee x \in B\}\)。只要在其中一个集合里就算。
  • 交集 (Intersection)：\(A \cap B = \{x | x \in A \wedge x \in B\}\)。必须同时在两个集合里。
    • 如果两个集合的交集是 \(\emptyset\)，则称这两个集合是不交的。
  • 相对补集 (差集, Difference)：\(A - B = \{x | x \in A \wedge x \notin B\}\)。在 \(A\) 里面，但是要把属于 \(B\) 的部分“抠掉”。
  • 对称差集 (Symmetric Difference)：期末高频考点，记作 \(A \oplus B\)。
    • 公式 1：\(A \oplus B = (A - B) \cup (B - A)\)。即只属于 \(A\) 或只属于 \(B\) 的元素。
    • 公式 2：\(A \oplus B = (A \cup B) - (A \cap B)\)。即把两者的并集挖去它们的交集。

2. 一元运算

  • 绝对补集：在给定全集 \(E\) 的前提下，\(\sim A = E - A = \{x | x \notin A\}\)。即“除了 \(A\) 以外的所有东西”。

四、 推广的并与交运算

本质是“剥洋葱”操作。设 \(A\) 是一个由集合构成的集合。

  • 广义并 (\(\cup A\))：把 \(A\) 里面所有小集合的元素全部倒出来，混成一个大集合。
    • 公式：\(\cup A = \{x | \text{存在} z, z \in A \wedge x \in z\}\)。
    • 示例：若 \(A = \{\{a, b, c\}, \{a, c, d\}\}\)，则 \(\cup A = \{a, b, c, d\}\)。
  • 广义交 (\(\cap A\))：找 \(A\) 里面所有小集合的公共元素。
    • 公式：\(\cap A = \{x | \text{对于任意的} z, \text{若} z \in A, \text{则} x \in z\}\)。
    • 示例：若 \(A = \{\{a, b, c\}, \{a, c, d\}\}\)，则 \(\cap A = \{a, c\}\)。

五、 集合运算的优先级

当表达式不带括号时，必须遵循以下运算优先级规则：

1. 运算分类

  • 一类运算：广义并 (\(\cup\))、广义交 (\(\cap\))、幂集 (\(P\))、绝对补 (\(\sim\))。
  • 二类运算：并 (\(\cup\))、交 (\(\cap\))、相对补 (\(-\))、对称差 (\(\oplus\))。

2. 顺序法则

  • 一类优先于二类。
  • 一类运算之间：由右向左顺序进行。例如 \(\sim P(A)\)，先计算幂集，再求补集。
  • 二类运算之间：没有括号时，按从左到右顺序进行。有括号时，括号内部优先级最高。

六、 集合运算的性质与算律

1. 十一大核心算律

  • 幂等律：\(A \cup A = A\), \(A \cap A = A\)
  • 交换律：\(A \cup B = B \cup A\), \(A \cap B = B \cap A\)
  • 结合律：\((A \cup B) \cup C = A \cup (B \cup C)\), \((A \cap B) \cap C = A \cap (B \cap C)\)

  • 分配律（极高频考点）：

    • \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
    • \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
    • 同一律：\(A \cup \emptyset = A\), \(A \cap E = A\)
    • 零律：\(A \cup E = E\), \(A \cap \emptyset = \emptyset\)
    • 排中律：\(A \cup \sim A = E\)
    • 矛盾律：\(A \cap \sim A = \emptyset\)
    • 吸收律：\(A \cup (A \cap B) = A\), \(A \cap (A \cup B) = A\)
    • 双重否定律：\(\sim\sim A = A\)

    • 德摩根律 （重点）：

    • 补集形式：\(\sim(B \cup C) = \sim B \cap \sim C\), \(\sim(B \cap C) = \sim B \cup \sim C\)

    • 差集形式：\(A - (B \cup C) = (A - B) \cap (A - C)\), \(A - (B \cap C) = (A - B) \cup (A - C)\)

2. 恒等式证明的“黄金套路” 在期末考试中，证明两个集合相等（例如 \(X = Y\)）通常有以下几种突破口：

  • 黄金转换公式（看到减号必用）：\(A - B = A \cap \sim B\)。做证明题时，第一步通常是将相对补运算（减号）转换为交集和绝对补的组合，这样就能全面使用结合律和分配律了。

  • 双向包含法（最严谨的保底方法）：

    1. 先证 \(X \subseteq Y\)：任取元素 \(x \in X\)，通过逻辑推导得出 \(x \in Y\)。
    2. 再证 \(Y \subseteq X\)：任取元素 \(x \in Y\)，通过逻辑推导得出 \(x \in X\)。

七、 有穷集的计数

容斥原理

  • 两集合公式：\(|A \cup B| = |A| + |B| - |A \cap B|\)
  • 三集合公式：\(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\)

八、课后习题

题目 1：化简 \((B - (A \cap C)) \cup (A \cap B \cap C)\)

核心技巧：差集转交集 \(\to\) 逆向分配律提取公因式。

推导步骤

  1. 原式 \(= (B \cap \sim(A \cap C)) \cup (B \cap (A \cap C))\) （相对补转换）
  2. \(= B \cap (\sim(A \cap C) \cup (A \cap C))\) （逆向分配律，提取 \(B \cap\)）
  3. \(= B \cap E\) （排中律）
  4. \(= B\) （同一律）

题目 2：证明 \(\sim((\sim A \cup \sim B) \cap \sim A) = A\)

核心技巧：连环使用德摩根律 \(\to\) 寻找吸收律。

推导步骤

  1. 左边 \(= \sim(\sim(A \cap B) \cap \sim A)\) （内部德摩根律：\(\sim A \cup \sim B = \sim(A \cap B)\)）
  2. \(= \sim\sim(A \cap B) \cup \sim\sim A\) （外部德摩根律，交变并）
  3. \(= (A \cap B) \cup A\) （双重否定律）
  4. \(= A\) （吸收律）
  5. = 右边

题目 3：证明 \(P(A) \cap P(B) = P(A \cap B)\) 以及 \(P(A) \cup P(B) \subseteq P(A \cup B)\)

任取元素 \(x\)：

  1. \(x \in P(A) \cap P(B)\)
  2. \(\iff x \in P(A) \wedge x \in P(B)\) （交集定义）
  3. \(\iff x \subseteq A \wedge x \subseteq B\) （幂集定义）
  4. \(\iff x \subseteq (A \cap B)\) （交集性质）
  5. \(\iff x \in P(A \cap B)\) （幂集定义）

任取元素 \(x\)：

  1. \(x \in P(A) \cup P(B)\)
  2. \(\iff x \in P(A) \vee x \in P(B)\) （并集定义，完全等价）
  3. \(\iff x \subseteq A \vee x \subseteq B\) （幂集定义，完全等价）
  4. \(\implies x \subseteq (A \cup B)\) （反推不成立）
  5. \(\iff x \in P(A \cup B)\) （幂集定义，完全等价）

反例：为什么这里不能写等号

  1. 令 \(A = \{1\}\), \(B = \{2\}\)。
  2. \(A \cup B = \{1, 2\}\)，显然 \(\{1, 2\} \in P(A \cup B)\)。
  3. 但 \(P(A) = \{\emptyset, \{1\}\}\)，\(P(B) = \{\emptyset, \{2\}\}\)。
  4. 因此 \(P(A) \cup P(B) = \{\emptyset, \{1\}, \{2\}\}\)。
  5. 显然 \(\{1, 2\} \notin P(A) \cup P(B)\)，故等号不成立。