集合论-离散基础概念简介

3. 集合论

集合 (Set)

集合论是离散数学的核心基础之一，由康托尔（Cantor）创立，用于描述对象的抽象集合。

定义

一个集合 (Set) 是一些确定的、互异的对象的整体，这些对象称为集合的元素 (Elements)。

• 记法：a∈A 表示“a是集合 A 的元素”。
• a∉A表示“a 不是集合 A 的元素”。

集合的表示方法

• 列举法：列出所有元素，如 A={1,2,3}。
• 描述法：用谓词定义元素特征，如 B={x∣x∈Z,x>0,x<5}，即正整数中小于 5 的数。

基本集合关系

基本集合运算

特殊集合

• 空集：∅ 或 {}，不包含任何元素。
• 全集：U，讨论问题时涉及的所有元素的集合。

集合论为函数、关系、图论、代数结构等提供了语言和基础。

集合的图形表达

假设存在以下集合:
全集U={1,2,3,4,5,6,7,8}
子集C={1,2} , D={3,4}

以上集合, 用图形表达后的结果如下:

全集 U
┌───────────────────────┐
│                       │
│   ┌─────────┐         │
│   │    C    │         │
│   │  {1,2}  │         │
│   └─────────┘         │
│                       │
│           ┌─────────┐ │
│           │    D    │ │
│           │  {3,4}  │ │
│           └─────────┘ │
│                       │
│     5    6    7    8  │
│                       │
└───────────────────────┘

二元关系 (Binary Relations)

二元关系是描述两个集合元素之间“关联”的数学工具。

基本定义

• 笛卡尔积 (Cartesian Product): 给定两个集合 A 和 B，它们的笛卡尔积 A × B 是所有有序对 (a, b) 的集合，其中 a ∈ A, b ∈ B。
• 二元关系 (Binary Relation): 从集合 A 到集合 B 的一个二元关系 R 是 A × B 的一个子集。如果 (a, b) ∈ R，我们说 "a 与 b 有关系 R"，记作 aRb。

示例: 设 A = {1, 2}, B = {x, y}。

• A × B = {(1,x), (1,y), (2,x), (2,y)}

• 定义关系 R 为“数字小于2且字母是x”，则 R = {(1,x)}。

• 因为 (1,x) ∈ R，所以 1 R x 成立。

• 关系的表示:

  • 集合表示法: 如上，R = {(1,x)}。

  • 关系矩阵: 行表示 A 的元素，列表示 B 的元素。有关系为 1，无关系为 0。

    R	x	y
    1	1	0
    2	0	0

  • 关系图 (有向图): 用顶点表示元素，有向边表示关系。

    1 ----> x
    
    (从 1 指向 x)
    

关系的性质

下表揭示的是集合 A 上的关系 R 具有哪些性质

这里具体解释一下这句话 集合 A 上的关系 R :
集合 A 上的二元关系 表示 笛卡儿积A × A 的二元关系
集合 A 上的二元关系R 表示 笛卡儿积A × A 的二元关系中的任意一个子集
所以集合 A 上的关系 R是有多个的, 以下表格中示例是多个子集中的一个,请注意别混淆

注意: 一个关系可以同时是自反和对称的（如上例），但不能同时是自反和反自反的（除非是空集）。

特殊的关系类型

• 等价关系 (Equivalence Relation): 一个关系如果同时满足自反性、对称性、传递性，则称为等价关系。它将集合划分成互不相交的块。

示例: 设 A = {1, 2, 3, 4}，定义关系 R 为“模 2 同余”，即 a R b 当且仅当 a 和 b 除以 2 的余数相同。

• R = {(1,1),(1,3),(3,1),(3,3), (2,2),(2,4),(4,2),(4,4)}
• 验证性质：
  • 自反：每个数和自己同余 √
  • 对称：如果 a 和 b 同余，则 b 和 a 同余 √
  • 传递：如果 a 和 b 同余，b 和 c 同余，则 a 和 c 同余 √
• 所以 R 是等价关系。

商集 A/R = {{1,3}, {2,4}}。

• 偏序关系 (Partial Order Relation): 一个关系如果同时满足自反性、反对称性、传递性，则称为偏序关系，通常记作 ≤。

示例: 设 A = {1, 2, 3, 6}，定义关系 ≤ 为“整除”，即 a ≤ b 当且仅当 a 整除 b。

• R = {(1,1),(2,2),(3,3),(6,6), (1,2),(1,3),(1,6), (2,6), (3,6)}
• 验证性质：
  • 自反：每个数整除自己 √
  • 反对称：如果 a 整除 b 且 b 整除 a，则 a=b √
  • 传递：如果 a|b 且 b|c，则 a|c √
• 所以这是一个偏序关系。

哈斯图 (Hasse Diagram): 用于简化表示偏序集。

   6
  / \
 2   3
  \ /
   1

(箭头省略，方向默认向上)
极小元: 1 (没有比它小的元素)
最小元: 1 (它是最小的)
极大元: 2, 3, 6? 6 比 2 和 3 大，但 2 和 3 之间不可比。所以极大元是 6。
最大元: 6 (它是最大的)

• 关系的运算

  • 逆关系 (Inverse): R⁻¹ = {(b, a) | (a, b) ∈ R}。

    • 示例：R = {(1,2), (3,4)}，则 R⁻¹ = {(2,1), (4,3)}。

  • 复合关系 (Composition): R ∘ S = {(a, c) | ∃b, (a, b) ∈ S 且 (b, c) ∈ R}。注意顺序：先 S，后 R。

    • 示例：S = {(1,2)}, R = {(2,3)}，则 R ∘ S = {(1,3)}。

  • 闭包 (Closure):

    • 自反闭包 r(R): 添加所有缺失的自环。r(R) = R ∪ I_A (I_A 是恒等关系)。
      • 示例：R = {(1,2)} on A={1,2}，则 r(R) = {(1,2), (1,1), (2,2)}。
    • 对称闭包 s(R): 添加所有“反向”边。s(R) = R ∪ R⁻¹。
      • 示例：R = {(1,2)}，则 s(R) = {(1,2), (2,1)}。
    • 传递闭包 t(R): 添加所有由传递性要求的边。t(R) = R ∪ R² ∪ R³ ∪ ...。
      • 示例：R = {(1,2), (2,3)}，则 R² = {(1,3)}，更高次幂为空。所以 t(R) = {(1,2), (2,3), (1,3)}。

函数 (Functions)

函数是一种特殊的二元关系，它要求每个输入对应唯一的输出。

基本定义

• 函数 (Function): 从集合 A 到集合 B 的函数 f 是一个从 A 到 B 的二元关系，满足：对于 A 中的每一个元素 a，在 B 中有且仅有一个元素 b 与之对应。记作 f: A → B。
• 定义域 (Domain): A。
• 陪域 (Codomain): B。
• 值域 (Range/Image): f(A) = {f(a) | a ∈ A} ⊆ B。

示例: 设 f: {1,2,3} → {a,b,c}，定义为 f(1)=a, f(2)=b, f(3)=a。

• 定义域: {1,2,3}
• 陪域: {a,b,c}
• 值域: {a,b} (注意：c 不在值域中)

函数的类型

函数的运算

• 函数的复合 (Composition): 给定 f: A → B 和 g: B → C，复合函数 g ∘ f: A → C 定义为 (g ∘ f)(a) = g(f(a))。顺序：先 f，后 g。

  • 示例：f: {1,2} → {a,b}, f(1)=a, f(2)=b；g: {a,b} → {x,y}, g(a)=x, g(b)=y。
  • 则 (g ∘ f)(1) = g(f(1)) = g(a) = x；(g ∘ f)(2) = g(b) = y。

• 逆函数 (Inverse Function):

  • 只有双射函数才有逆函数。
  • 如果 f: A → B 是双射，则存在 f⁻¹: B → A，使得 f⁻¹(f(a)) = a 且 f(f⁻¹(b)) = b。

  示例: f: {1,2,3} → {a,b,c}, f(1)=a, f(2)=b, f(3)=c (双射)。

  • 逆函数 f⁻¹: {a,b,c} → {1,2,3}, f⁻¹(a)=1, f⁻¹(b)=2, f⁻¹(c)=3。

基数 (Cardinality)