集合论--形式化语言里的汇编码

如果一阶逻辑是数学这门形式化语言里的机器码，那么集合论就是数学这门形式化语言里的汇编码。

基本思想：从集合出发构建所有其它。

• 构建自然数
• 构建整数
• 构建有理数
• 构建实数
• 构建有序对、笛卡尔积、关系、函数、序列等
• 构建确定有限自动机(DFA)

全景图

         常量+变量+谓词+量词+函数           谓词：属于
命题逻辑------------------------->一阶逻辑----------->集合论-->所有其它

---

从集合出发构建一切

在数学和计算机科学中，集合论是构建一切的基础。通过集合，我们可以定义和描述几乎所有数学对象和计算机科学中的结构。本文将从集合出发，逐步展示如何构建自然数、整数、有理数、实数，以及更复杂的数学和计算机科学概念。

---

1. 集合论的基础

集合论的核心是集合和隶属关系（$\in$）。集合是一些确定的、不同的对象的整体，这些对象称为集合的元素。通过集合，我们可以定义以下基本概念：

• 空集（$\varnothing$）：不包含任何元素的集合。
• 子集（$A\subseteq B$）：如果集合 $A$ 的所有元素都属于集合 $B$，则 $A$ 是 $B$ 的子集。
• 并集（$A\cup B$）：包含所有属于 $A$ 或 $B$ 的元素的集合。
• 交集（$A\cap B$）：包含所有同时属于 $A$ 和 $B$ 的元素的集合。
• 差集（$A\setminus B$）：包含所有属于 $A$ 但不属于 $B$ 的元素的集合。
• 补集（$\overline{A}$）：包含所有不属于 $A$ 的元素的集合。

---

2. 从集合构建自然数

自然数（$\mathbb{N}$）是数学中最基本的数集之一。我们可以通过集合递归地定义自然数：

• $0=\varnothing$（空集）。
• 1 = { 0 } = { ∅ } 1 = \{0\} = \{\emptyset\} 1={0}={∅}。
• 2 = { 0 , 1 } = { ∅ , { ∅ } } 2 = \{0, 1\} = \{\emptyset, \{\emptyset\}\} 2={0,1}={∅,{∅}}。
• 3 = { 0 , 1 , 2 } = { ∅ , { ∅ } , { ∅ , { ∅ } } } 3 = \{0, 1, 2\} = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\} 3={0,1,2}={∅,{∅},{∅,{∅}}}。
• 以此类推。

通过这种方式，每个自然数都是一个集合，且自然数的顺序可以通过集合的包含关系来定义。

3. 从自然数构建整数

整数（$\mathbb{Z}$）包括自然数及其负数。我们可以通过有序对来定义整数：

• 每个整数 $z$ 可以表示为有序对 $(a,b)$，其中 $a$ 和 $b$ 是自然数。
• 整数 $z$ 的值定义为 $a-b$。
• 例如，$(3,0)$ 表示 $3$，$(0,3)$ 表示 $-3$。

通过这种方式，整数可以通过自然数的有序对来构建。

4. 从整数构建有理数

有理数（$\mathbb{Q}$）是可以表示为两个整数之比的数。我们可以通过有序对来定义有理数：

• 每个有理数 $q$ 可以表示为有序对 $(a,b)$，其中 $a$ 和 $b$ 是整数，且 $b\ne 0$。
• 有理数 $q$ 的值定义为 $\frac{a}{b}$。
• 例如，$(3,2)$ 表示 $\frac{3}{2}$。

通过这种方式，有理数可以通过整数的有序对来构建。

5. 从有理数构建实数

实数（$\mathbb{R}$）包括有理数和无理数。实数的构建较为复杂，通常通过戴德金分割或柯西序列来定义：

• 戴德金分割：将有理数集 $\mathbb{Q}$ 分成两个非空集合 $A$ 和 $B$，使得 $A$ 中的所有元素都小于 $B$ 中的所有元素。每个实数对应一个戴德金分割。
• 柯西序列：实数可以定义为有理数柯西序列的极限。柯西序列是一种收敛的有理数序列。

通过这种方式，实数可以通过有理数的结构来构建。

6. 从集合构建更复杂的数学对象

通过集合，我们可以定义更复杂的数学对象：

• 有序对：有序对 $(a,b)$ 可以定义为集合 { { a } , { a , b } } \{\{a\}, \{a, b\}\} {{a},{a,b}}。
• 笛卡尔积：集合 $A$ 和 $B$ 的笛卡尔积 $A\times B$ 是所有有序对 $(a,b)$ 的集合，其中 $a\in A$ 且 $b\in B$。
• 关系：关系是笛卡尔积的子集。例如，等价关系、偏序关系等。
• 函数：函数是一种特殊的关系，满足每个输入对应唯一的输出。
• 序列：序列是函数的一种，定义域为自然数集 $\mathbb{N}$。
• 元组：元组是有限序列，可以表示为有序对的嵌套。

---

7. 从集合构建计算机科学概念

集合论在计算机科学中也有广泛应用。以下是一些例子：

• 确定有限自动机（DFA）：
  • DFA 可以表示为一个五元组 $(Q,\Sigma ,\delta ,q_0,F)$。
    • $Q$ 是状态的有限集合。
    • $\Sigma$ 是输入符号的有限集合。
    • $\delta$ 是转移函数，定义为 $\delta :Q\times \Sigma \to Q$。
    • $q_0$ 是初始状态。
    • $F$ 是接受状态的集合。
  • 通过集合，DFA 的所有组成部分都可以被严格定义。

8. 总结

从集合出发，我们可以构建几乎所有数学和计算机科学中的结构：

1. 自然数通过空集和递归定义。
2. 整数通过自然数的有序对。
3. 有理数通过整数的有序对。
4. 实数通过有理数的戴德金分割或柯西序列。
5. 更复杂的数学对象（如有序对、笛卡尔积、关系、函数、序列、元组）通过集合的组合和操作。
6. 计算机科学概念（如 DFA）通过集合的严格定义。

集合论为数学和计算机科学提供了一个统一的框架，使得我们能够以严格和抽象的方式描述和操作各种对象。通过集合，我们可以从最基础的概念出发，逐步构建出复杂的数学和计算机科学结构。