Skip to content

04_Basic Structures

一、 集合与集合操作 (Sets)

1. 基础概念与表示

  • 集合 (Set)：无序的对象集合。

  • 元素 (Elements)：集合包含的对象，使用 \(a \in A\) 属于或 \(a \notin A\) 不属于表示。

  • 表示方法：

    • 列举法 (Roster)：用大括号列出所有元素（顺序和重复不重要）。

    • 构造法 (Set-Builder)：通过谓词属性定义，如 \(S = \{x \mid P(x)\}\)。

    • 区间表示法：用于实数子集，如闭区间 \([a, b]\)，开区间 \((a, b)\)。

  • 特殊集合：全集 (\(U\)) 包含当前上下文的所有事物；空集 (\(\emptyset\)) 包含零个元素。

2. 集合关系与高级概念

  • 相等 (\(A = B\))：包含完全相同的元素（逻辑上 \(\forall x(x \in A \leftrightarrow x \in B)\) 或 \(A \subseteq B \land B \subseteq A\)）。

  • 子集 (\(A \subseteq B\))：\(A\) 的所有元素都属于 \(B\)。空集和集合本身是自身的子集。

  • 真子集 (\(A \subset B\))：\(A \subseteq B\) 且 \(A \neq B\)。

  • 基数 (Cardinality, \(|S|\))：有限集 \(S\) 中不同元素的个数。

  • 幂集 (Power Set, \(\mathcal{P}(A)\))：集合 \(A\) 的所有子集构成的集合。若 \(|A| = n\)，则 \(|\mathcal{P}(A)| = 2^n\)。

  • 笛卡尔积 (\(A \times B\))：所有有序对 \((a, b)\) 的集合，其中 \(a \in A \land b \in B\)。

3. 集合操作与定律

  • 核心操作：并集 (\(A \cup B\))、交集 (\(A \cap B\))、补集 (\(\bar{A}\))、差集 (\(A - B = A \cap \bar{B}\))、对称差 (\(A \oplus B\))。若 \(A \cap B = \emptyset\)，则称两集合不相交 (Disjoint)。

  • 容斥原理：\(|A \cup B| = |A| + |B| - |A \cap B|\)。

  • 集合恒等式：对应于命题逻辑定律，包含恒等律、支配律、幂等律、德·摩根定律 (\(\overline{A \cup B} = \bar{A} \cap \bar{B}\))、分配律、吸收律等。

  • 计算机表示：通过位串 (Bit strings) 表示集合，并集对应按位或 (OR)，交集对应按位与 (AND)。

二、 函数 (Functions)

1. 基础定义

  • 函数 (\(f: A \rightarrow B\))：将集合 \(A\)（定义域 Domain）中的每个元素唯一映射到集合 \(B\)（陪域 Codomain）中的一个元素。

  • 术语：\(b = f(a)\) 中，\(b\) 是 \(a\) 的像 (Image)，\(a\) 是 \(b\) 的原像 (Preimage)。所有像的集合称为值域 (Range, \(f(A)\))。

2. 函数的映射类型

  • 单射/一对一 (Injective)：\(\forall a, b [f(a) = f(b) \rightarrow a = b]\)，定义域中没有两个不同元素映射到同一个像。

  • 满射/映上 (Surjective)：值域与陪域完全相等，陪域中每个元素都有原像。

  • 双射/一一对应 (Bijective)：既是单射又是满射。

3. 函数操作与特殊函数

  • 逆函数 (\(f^{-1}\))：仅当 \(f\) 是双射时存在，\(f^{-1}(y) = x \iff f(x) = y\)。

  • 复合函数 (\(f \circ g\))：\((f \circ g)(x) = f(g(x))\)。仅当 \(g\) 的值域是 \(f\) 的定义域的子集时有效，通常不满足交换律。

  • 特殊函数：

    • 向下取整 (\(\lfloor x \rfloor\)) 和 向上取整 (\(\lceil x \rceil\))：分别映射到小于等于/大于等于 \(x\) 的最近整数。

    • 阶乘 (\(n!\))：前 \(n\) 个正整数的乘积，大数估算可用斯特林公式。

  • 偏函数 (Partial Functions)：仅在定义域的某个特定子集上定义，如果是整个集合则称为全函数 (Total Function)。

三、 序列与求和 (Sequences and Summations)

1. 序列 (Sequences)

  • 定义：从整数子集到集合 \(S\) 的函数，项记为 \(a_n\)。

  • 常见数列：等差数列 (\(a_n = a + nd\))；等比数列 (\(a_n = ar^n\))。

  • 递推关系 (Recurrence Relations)：通过之前的一项或多项来递归定义 \(a_n\)。包含递推方程和初始条件（如斐波那契数列 \(f_n = f_{n-1} + f_{n-2}\)）。

  • 求解：迭代法（向前替换或向后替换），最终推导出一个闭式公式。

2. 求和 (Summations)

  • 符号：使用 \(\sum\) 表示求和，\(\prod\) 表示求积。

  • 几何级数公式 (Geometric Series)：\(\sum_{j=0}^{n} ar^j = \frac{ar^{n+1} - a}{r - 1}\)（当 \(r \neq 1\) 时）。

  • 无穷几何级数：当 \(|x| < 1\) 时，\(\sum_{k=0}^{\infty} x^k = \frac{1}{1 - x}\)。

四、 集合基数与无穷 (Set Cardinality)

1. 基数比较

  • 定义：\(|A| = |B|\) 意味着两集合间存在双射；\(|A| \leq |B|\) 意味着存在单射。

  • 可数集 (Countable)：有限集或与正整数集 \(\mathbb{Z}^+\) 具有相同基数 (\(\aleph_0\)) 的无穷集。

    • 示例：偶数、整数 (\(\mathbb{Z}\))、正有理数 (\(\mathbb{Q}^+\))、有限字母表上的所有字符串、所有 Java 程序。

2. 不可数集与康托尔对角线法

  • 不可数集 (Uncountable)：无法与 \(\mathbb{Z}^+\) 建立双射的集合，如实数集 \(\mathbb{R}\) 或区间 \((0, 1)\)（基数为 \(\aleph_1\)）。

  • 康托尔对角线法 (Cantor's Diagonalization)：反证法。假设 \((0, 1)\) 是可数的并列出所有小数，通过刻意修改对角线上的每个数字 (\(x_i \neq d_{ii}\))，构造出一个绝对不在列表中的新实数，从而推翻可数假设。

3. 核心定理与思想实验

  • Schröder-Bernstein 定理：若 \(|A| \leq |B|\) 且 \(|B| \leq |A|\)，则 \(|A| = |B|\)。

  • 幂集定理：任意集合的幂集基数严格大于原集合基数。

  • 连续统假设 (CH)：断言不存在严格介于 \(\aleph_0\) 和 \(\aleph_1\) 之间的基数。

  • 希尔伯特旅馆：思想实验，展示可数无穷集的反直觉算术（如 \(\aleph_0 + 1 = \aleph_0\)）。

  • 可计算性：Java 程序数量可数，而函数数量不可数，因此必然存在不可计算的函数。

五、 矩阵 (Matrices)

1. 矩阵基础与算术

  • 定义：\(m\) 行 \(n\) 列的矩形数字阵列，用 \(A = [a_{ij}]\) 表示。

  • 加法 (\(A + B\))：对应元素相加，仅限同尺寸矩阵。

  • 乘法 (\(AB\))： 第 \(i\) 行与第 \(j\) 列的对应元素乘积之和。仅当第一个矩阵的列数等于第二个矩阵的行数时有效，且不满足交换律 (\(AB \neq BA\))。

2. 特殊矩阵

  • 单位矩阵 (\(I_n\))：主对角线为 1，其余为 0 的方阵。\(AI_n = A\)。

  • 转置矩阵 (\(A^t\))：行列互换，\(b_{ij} = a_{ji}\)。若 \(A = A^t\)，则是对称矩阵 (Symmetric Matrix)。

3. 0-1 矩阵 (Zero-One Matrices)

基于布尔算术操作（\(\land\) 为 AND，\(\lor\) 为 OR）：

  • 并 (Join, \(A \lor B\)) 和 交 (Meet, \(A \land B\))：对应元素分别执行布尔 OR 和 AND 操作。

  • 布尔乘积 (\(A \odot B\))：运算过程类似于标准矩阵乘法，但用布尔 \(\land\) 代替乘法，用 \(\lor\) 代替加法。

  • 布尔幂 (\(A^{[r]}\))：矩阵 \(A\) 自身进行 \(r\) 次布尔乘积。通常经过一定迭代后会趋于固定状态。