Coursera离散数学概论笔记（四）： 集合论之集合代数

本文目录

• 1 集合论与无限
• 1.1 集合论
• 1.2 无限
• 1.3 集合论的历史发展
• 2 集合基本概念
• 2.1 定义
• 2.2 集合的基本概念
• 2.2.1 成员
• 2.2.2 空集
• 2.2.3 有限集（finite sets）
• 2.2.4 基数（cardinality）
• 2.3 规定集合的方式
• 2.4 集合的三大公理
• 3 子集合
• 3.1 子集合定义
• 3.2 子集合性质
• 3.3 真子集
• 4 集合运算
• 4.1 集合运算定义
• 4.2 集合基本运算
• 4.3 交和并运算性质
• 4.4 差和补运算性质
• 4.5 集合运算和子集的关系
• 4.6 幂集运算
• 5 集合族及运算
• 5.1 集合族与标志集
• 5.2 集合族的运算
• 5.3 集合族运算性质
• 6 归纳定义
• 6.1 集合的归纳定义
• 6.2 归纳定义的例子
• 7 自然数定义
• 8 归纳原理
• 8.1 定义
• 9 数学归纳法
• 9.1 定义
• 9.2 数学归纳法的变种
• 9.3 数学归纳法的例子
• 9.4 数学归纳法的正确性证明

---

1 集合论与无限

1.1 集合论

集合论：集合论是以集合概念为基础，研究集合的一般性质的数学分支学科。“集合”是比“数”更简单的概念，集合论试图从研究集合出发，定义“数”和数的“运算”，进而发展到整个数学，是研究数学基础的学科。

集合：集合是简单而又基本的不作定义的初始概念。一般来说，集合是一些确定的、相异的事物的总体。

按照集合中事物数目是否有限，可以分为有限集合和无限集合。无限集合是集合论研究的主要对象，也是集合论建立的关键和难点。

1.2 无限

集合论的全部历史都是围绕无限概念展开的。

两种无限：

• 潜无限：作为过程的无限，指永远延伸、永远完成不了的进程，如自然数序列 $1,2,3,...,n,...$1,2,3,...,n,...
• 实无限：作为已完成的整体的无限，如自然数全体组成的整体 $(1,2,3,...,n,...)$(1,2,3,...,n,...)

1.3 集合论的历史发展

集合论发展的大事件：

1. 公元前 5 世纪，芝诺提出二分法悖论、阿基里斯追乌龟悖论等悖论

2. 亚里士多德最先提出要区分潜无限和实无限，并认为只存在潜无限。

3. 普罗克拉斯在研究直径分园问题时发现直径数量和将圆分成部分的数量有一一对应的关系

4. 伽利略发现不等长线段上的点可以构成一一对应的关系

5. 捷克数学家波尔察诺最先明确承认并拥护无限集合的概念，并将一一对应关系称作等价关系

6. 1874年，康托尔发表了《论所有实代数数集合的一个性质》，较全面阐述了无限集合思想，朴素集合论成为整个数学的基础

7. 罗素悖论的发现，产生了第三次数学危机

8. 为了在朴素集合论中消除悖论，人们想了各种办法来限制“病态集合”的产生，最成功的是采用希尔伯特公理化思想对朴素集合论进行公理化，公理化集合论产生发展以后，普遍认为它给数学提供了一个可靠的基础

2 集合基本概念

2.1 定义

集合（set）：做为整体识别的、确定的、互相区别的一些对象的总体。其具有以下 3 个性质：

• 整体识别：不再分割
• 确定：属于或者不属于整体
• 互相区别：各异的对象

集合的记号：“ $\{,\}${,} “

几个集合的例子：

2.2 集合的基本概念

2.2.1 成员

组成集合的对象称为成员（member） 或者元素（element）。元素可以是任何具体或者抽象的事物，元素也可以是集合。

元素和集合的隶属关系：

• 当对象 a 是集合 A 的成员时，称 a 属于 A ，记作” $a \in A$a∈A “。
• 当对象 a 不是集合 A 的成员时，称 a 不属于 A ，记作” $¬ (a \in A)$¬(a∈A) “或者” $a \notin A$a∈/​A “。

2.2.2 空集

没有任何元素的特定集合称为空集，记作 $\empty$∅ ，$\empty = \{\}=\{x|x \neq x\}$∅={}={x∣x​=x} （谓词公式为一永假式）。

2.2.3 有限集（finite sets）

空集和只含有有限多个元素的集合称为有限集，否则，称作无限集（infinite sets）。

2.2.4 基数（cardinality）

有限集合中成员的个数称为集合的基数（无限集合的基数定义更为复杂）。

集合 $A$A 的基数记作 $|A|$∣A∣ 。

2.3 规定集合的方式

规定集合的方式有 3 种：

• 列举法：将所有元素列举，例如：$A = \{ 1, 2, 3 \}$A={1,2,3}
• 描述法：将集合中的元素的特征用谓词公式描述，例如：$A = \{x|p(x)\}$A={x∣p(x)} 表示 $x \in A$x∈A 当且仅当 $P(x)$P(x)
• 归纳法（后面的章节会专门说明）

一些集合规定的例子：

2.4 集合的三大公理

• 外延公理（extensionality axiom）：两个集合 A 和 B 相等当且仅当它们具有相同的元素。

  用命题公式表示为：$A=B \leftrightarrow \forall x(x\in A \leftrightarrow x \in B)$A=B↔∀x(x∈A↔x∈B)

  说明了集合元素的无序性，以及集合表示形式的不唯一性。

• 概括公理（comprehension axiom）：对于任意个体域 U ，任一谓词公式 P 都确定一个以该域中对象为元素的集合 S 。

  集合 S 可以表示为：$b$b

  概括公理规定了集合成员的确定性。

• 正规公理（regularity axiom）：不存在集合 $A_1,A_2,A_3,...$A1​,A2​,A3​,... 使得：$...\in A_3 \in A_2 \in A_1$...∈A3​∈A2​∈A1​ 。

  直观来说，就是集合有限可分，个体域的元素是“基本粒子”。

  正规公理确立了元素和集合的不同层次性，集合不能是自己的成员，排除了 $A=\{A\}$A={A} 这样的“病态“集合。

3 子集合

3.1 子集合定义

如果 A 的每一个元素都是 B 的元素，那么集合 A 称作集合 B 的子集合，记作 $A \subseteq B$A⊆B 。

用命题公式可以表示成：$\forall x(x\in A \rightarrow x\in B)$∀x(x∈A→x∈B)

集合的两个基本关系：隶属和包含

子集合的例子：

3.2 子集合性质

• 定理1：对于任意集合 A 和 B，$A=B$A=B 当且仅当 $A\subseteq B$A⊆B 且 $B \subseteq A$B⊆A 。

  ​ 特别的，对于任意集合 A ，有 $A \subseteq A$A⊆A 。

• 定理2：设 A,B,C 为任意集合，若 $(A \subseteq B) \bigwedge (B \subseteq C)$(A⊆B)⋀(B⊆C) ，则有 $A \subseteq C$A⊆C 。

• 定理3：对于任意集合 A ，$A \subseteq U$A⊆U 。

• 定理4：对于任何集合 A ，$\empty \subseteq A$∅⊆A 。

• 定理5：空集是唯一的。

• 定理6：设 A 为一有限集合，$|A|=n$∣A∣=n ，那么 A 的子集个数为 $2^n$2n 。

3.3 真子集

如果 $A \subseteq B$A⊆B ，且 $A \neq B$A​=B，记作 $A \subset B$A⊂B 。

空集是所有非空集合的真子集。

4 集合运算

4.1 集合运算定义

集合运算：以集合作为运算对象，结果还是集合的运算。

4.2 集合基本运算

• 并运算（union）：$\cup$∪ （定义：$A \cup B = \{x|x \in A \bigvee x\in B\}$A∪B={x∣x∈A⋁x∈B}）
• 交运算（intersection）：$\cap$∩（定义：$A \cap B = \{x| x \in A \bigwedge x \in B\}$A∩B={x∣x∈A⋀x∈B}）
• 差运算（difference）：$-$−（定义：$A - B = \{x| x \in A \bigwedge x \notin B\}$A−B={x∣x∈A⋀x∈/​B}）
• 补运算（complement）：~（定义：$A$A ~ $B = \{x| x \notin A\}$B={x∣x∈/​A}

4.3 交和并运算性质

4.4 差和补运算性质

4.5 集合运算和子集的关系

4.6 幂集运算

对任意集合 $A$A ，$\rho (A)$ρ(A) 称作 $A$A 的幂集，定义为：$\rho (A) = \{x|x \subseteq A\}$ρ(A)={x∣x⊆A} 。

$\rho (A)$ρ(A) 即为 $A$A 的所有子集作为元素构成的集合。

设 $A,B$A,B 为任意集合，$A \subseteq B$A⊆B 当且仅当 $\rho(A) \subseteq \rho(B)$ρ(A)⊆ρ(B) 。

5 集合族及运算

5.1 集合族与标志集

集合族（collections）：如果集合 C 中的每个元素都是集合，称 C 为集合族。

标志集（index set）：如果集合族 C 可以表示为某种下标的形式 $C = \{S_d|d \in D\}$C={Sd​∣d∈D} ，那么这些下标组成的集合 D 称作集合族 C 的标志集。标志集可以是自然数或是某些连续符号。

举几个集合族和标志集的例子：

5.2 集合族的运算

• 广义并：集合族中所有集合的并集 $\cup C = \{x| \exist S(S\in C\bigwedge x\in S)\}$∪C={x∣∃S(S∈C⋀x∈S)}
• 广义交：集合族中所有集合的交集 $\cap C = \{x| \forall S(S\in C\rightarrow x\in S)\}$∩C={x∣∀S(S∈C→x∈S)}

如果 $C$C 恰含两个集合 A，B，则：$\cup C= A\cup B, \cap C = A\cap B$∪C=A∪B,∩C=A∩B

有标志集的表示方法（ $C = \{A_d|d \in D\}$C={Ad​∣d∈D} ）：$\cap C = \cap _{d \in D}A_d,\cup C = \cup _{d \in D}A_d$∩C=∩d∈D​Ad​,∪C=∪d∈D​Ad​

举两个集合族运算的例子：

5.3 集合族运算性质

6 归纳定义

6.1 集合的归纳定义

归纳定义（inductive definition） 由以下 3 条条款构成：

• 基础条款：规定某些元素为待定义集合成员，集合其他元素可以从基本元素出发逐步确定。
• 归纳条款：规定由已确定的集合元素去进一步确定其他元素的规则。
• 终极条款：规定待定义集合只含有基础条款和归纳条款所确定的成员。

基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员。

终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象。

6.2 归纳定义的例子

7 自然数定义

（注：这里举的例子比较具体，因此直接贴上PPT）

8 归纳原理

8.1 定义

设集合 A 是归纳定义的集合，要证明 A 中所有元素具有性质 P ，即：$\forall x(x \in A \rightarrow P(x))$∀x(x∈A→P(x)) ，可以进行如下证明：

• 归纳基础：针对归纳定义的基础条款，证明基础条款中的所有元素均使 $P(x_0)$P(x0​) 真
• 归纳推理：证明归纳条款是“保持性质 P 的”，即在假设归纳条款中已确定元素 $x$x 使 $P(x)$P(x) 真的前提下，证明用归纳条款中的操作 $g$g 所生成的 $g(x)$g(x) 依然有性质 P ，即 $P(g(x))$P(g(x)) 为真。

证明的例子：

9 数学归纳法

9.1 定义

数学归纳法是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。

既然自然数集合也是归纳定义的，对于自然数的一些性质，也可以通过归纳原理来证明。

以下提及的数学归纳法均指第一数学归纳法，具体步骤如下：

• 归纳基础：证明 $P(0)$P(0) 为真
• 归纳过程：对于任意 $k \geq 0$k≥0 ，假设 $P(k)$P(k) 为真时，推出 $P(k+1)$P(k+1) 也为真
• 结论：所有自然数 $n$n 都使 $P(n)$P(n) 为真

9.2 数学归纳法的变种

• 起始于任意自然数 $n_0$n0​ 的数学归纳法：证明所有大于等于 $n_0$n0​ 的自然数都具有性质 P 。

• 起始于多个自然数的数学归纳法：比如：

  • 归纳基础：证明 $P(0),P(1)$P(0),P(1) 真
  • 归纳过程：对于任意 $k \geq 0$k≥0 ，假设 $P(k)$P(k) 为真时，推出 $P(k+2)$P(k+2) 也为真
  • 结论：所有自然数具有性质 P

• 允许有参变量的数学归纳法：对于二元谓词 $P(m,n)$P(m,n) ，证明对于一切自然数 $m,n$m,n 都为真，可以视情况只对一个变量进行归纳，另一个变量作为参数。

9.3 数学归纳法的例子

9.4 数学归纳法的正确性证明