集合论基础

Ciara Nightingale

ZK 数学 101：集合论

学习集合论的基础知识，从有限集和无限集到集合运算和函数，这对于理解 ZK 证明中的密码学结构至关重要。 集合论是数学的一个分支，研究对象的集合，这些对象称为集合。 它提供了处理数学对象（整数、有理数等）集合所需的语言和结构。虽然最初是抽象的，但当我们稍后探索密码系统中使用到的群、环和域时，这些概念将是至关重要的。

本文是数学文章系列的第二篇，该系列文章讲授理解零知识证明数学所需的概念和术语。

本系列文章并非旨在作为学习所概述数学主题的独立、结论性的资源。相反，它是一个概述，旨在分享理解零知识证明和密码学所需的高级概念。如需更详细的分析，可以在每篇文章末尾的参考部分找到链接。

另请注意，为了简单起见，省略了定理和定义的数学证明。如果你有兴趣，请使用链接的资源或你最喜欢的 AI 助手来了解如何从第一性原理推导出这些概念。

话虽如此，让我们开始吧！

集合论

集合是不同元素的集合， 这意味着它不能包含重复的元素。 元素可以是任何类型，例如数字、字母、对象等，只要集合中的每个元素都是唯一的。 这就是集合论的魅力（和怪异之处）：它在设计上非常通用。

• 元素： 属于集合的对象。 例如，1 是整数无限集合的一个元素，用符号 Z 表示。 每个元素必须与其他所有元素不同：元素不能重复。

• 集合： 用花括号表示：{}，例如，{1,2,3}。

• 基数： 集合包含的元素数量。 例如，集合 {1,2,3} 的基数为3。 这也称为集合的阶。

有限集和无限集

无限集 包含无限数量的元素，并且是非有限的（哇哦，打赌你不知道 - 抱歉，英国式的讽刺忍不住了）。 例如，考虑数轴：它在一个或两个方向上永远延伸。 没有一个自然数可以表示无限集中元素的总数——根据定义，它是无限的。

无限集有两种类型：可数无限集和不可数无限集。

1. 可数无限集 可以 与自然数（用于计数和排序的正整数）建立一一对应关系。 换句话说，集合的元素可以按序列 {1,2,3,…} 列出，其中每个元素与唯一的自然数配对。

   • 形式上，这意味着集合和自然数集合之间存在双射函数（我们将很快介绍）。 任何可数无限集的基数与自然数集合的基数相同。

   • 这意味着即使集合是无限的，它仍然可以被排序，并且它的元素可以系统地列出，没有任何间隙。

   • 可数无限集的例子：

     • 整数 ( Z)： 整数可以按序列列出，例如 {0,1,−1,2,−2,3,−3,…}。

     • 正整数 ( N+)： 正整数集合可以列为 {1,2,3,…}。

     • 自然数 ( N)： 自然数集合可以列为 {0,1,2,…}。

     • 有理数 ( Q)：所有有理数的集合，用 {pq∣p and q are integers, q≠0} 表示。尽管它们在数轴上密集排列，但仍然可以枚举它们。如果你想查看解释有理数为什么 是可数无限的证明，你应该阅读康托尔的对角化论证。

2. 不可数无限集 不能 与自然数建立一一对应关系。 这意味着无法像可数无限集那样列出它们的所有元素。

   • 一个典型的例子是 0 和 1 之间的实数集合。 尽管此区间内有无数个有理数 （可以 列出），但该集合也包含无理数。 无理数 是具有非重复、非终止十进制展开的数字，无法表示为整数的比率 pq（例如 e 或 π），并且它们无法捕获在任何列表中。 即使有理数是可数的，但当你将它们与无数个无理数结合起来时，整个集合就变得不可数了。

   • 这已由 康托尔的对角论证 证明，该论证表明，即使你尝试列出 0 和 1 之间的所有实数，你始终可以构造一个不在列表中的新数字，这意味着该列表不完整。因此，无论你的方法多么聪明，你都无法为 0 和 1 之间的每个实数分配唯一的自然数标签。

   • 这就是使实数集合成为不可数无限集合 的原因：它的大小（或基数）严格大于 自然数或有理数，这两者都是可数无限集合。 毕竟， “有些无限比其他无限更大” 确实是真的。

   • 不可数无限集的例子：

     • 实数 ( R)： 任意两个不同实数（例如，0 和 1 之间）之间的实数集合是不可数无限的。此区间内有无数个实数，并且无法将它们全部按顺序排列。

     • 复数 ( C)： 复数集合是不可数无限集合，因为它包括实部和虚部的所有可能组合。

一个有限集具有一个特定的，可数的 元素数量。 它的基数是一个整数，可以被精确地确定。

• 有限集示例：
  • {红色，蓝色，黄色} - 原色。
  • {星期一,…,星期日} — 一周中的几天。
  • {0,1,2,…,23} — 一天中的小时数。
  • 整数模 n 的余数集合（其中 n 是某个整数）。 例如，{0,1,2,3,4} 是模 5 的整数集合, 表示为 Z5。 现在需要理解的重要一点是，这种类型的集合在密码学中最常用，并且随着我们深入研究这些主题，它对于零知识证明至关重要的作用将变得更加清晰。

子集

如果集合 A 的每个元素也是集合 B 的一个元素，那么 A 是 B 的一个子集，记为 A⊆B。

• 真子集：如果 A⊆B 并且 A≠B（意味着 B 至少有一个元素 A 没有），那么 A 是 B 的一个真子集，记为 A⊂B。

• 空集：空集，记为 ∅ 或 {}，是每个集合的子集。

• 幂集：集合 S 的幂集，记为 P(S) 或 2S，是 S 所有可能子集的集合，包括空集和 S 自身。

  • 基数：对于基数为 n 的有限集，幂集的基数为 2n。 这意味着该集合有 2n 个可能的子集。

  • 示例：如果 S=a,b,c，那么 P(S)={∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

子集的性质：

1. 传递性：如果 A 是 B 的子集，并且 B 是 C 的子集，那么 A 也必须是 C 的子集。用数学符号表示，这等价于：

2. 如果 A⊆B 且 B⊆C，则 A⊆C。

3. 自反性：每个集合都是其自身的子集，即 A⊆A。

4. 反对称性：如果 A 是 B 的子集，并且 B 是 A 的子集，那么 A 必须等于 B。或者，用数学符号表示，这等价于： 如果 A⊆B 且 B⊆A，则 A=B。

超集

如果集合 B 包含集合 A 的所有元素（可能还有更多），那么 B 是 A 的超集，记为 B⊇A。

• 等价性：B⊇A 等价于 A⊆B（它们从不同的角度表达相同的关系）。

• 真超集：如果 B⊇A 并且 B≠A（意味着 B 至少有一个元素 A 没有），那么 B 是 A 的一个真超集，记为 B⊃A。

• 全集：在给定的上下文中，全集（通常表示为 U）是所考虑的所有集合的超集。

超集的性质：

1. 传递性：如果 C⊇B 且 B⊇A，则 C⊇A。

2. 自反性：每个集合都是其自身的超集，即 A⊇A

3. 反对称性：如果 B⊇A 且 A⊇B，则 A=B。

集合运算、关系和函数

以下关于集合运算、关系和函数的部分提供了一些数学术语，你在阅读 ZKP 文献时可能会偶尔遇到。 这将使你基本熟悉，以帮助你在论文中浏览更广泛的数学背景。 将此视为纯粹的参考指南：

基本集合运算

集合运算允许我们组合和操作集合以创建新集合。

• 并集 (∪)：集合 A 和 B 的并集，记为 A∪B，是由属于 A 或 B 或两者的所有元素组成的集合。

  • 形式上：A∪B={x∣x∈A 或 x∈B}

  • 其中 ∣ 在数学符号中表示 “使得”，∈ 表示 “是...的一部分”。 所以这个符号表示我们定义了一个包含所有元素 x 的集合，使得 x 是 A 的一个成员 OR x 是 B 的一个成员。 ‍

  • 示例：{1,2,3}∪{3,4,5}={1,2,3,4,5}

• 交集 (∩)：集合 A 和 B 的交集，记为 A∩B，是由属于 A 且 B 的所有元素组成的集合。

  • 形式上：A∩B={x∣x∈A 且 x∈B}。

  • 这个符号表示我们定义了一个包含所有元素 x 的集合，使得 x 是 A 的一个成员 AND x 是 B 的一个成员。

  • 示例：{1,2,3}∩{3,4,5}={3}

• 差集 (∖)：集合 A 和 B 的差集，记为 A∖B，是由属于 A 但不属于 B 的所有元素组成的集合。

  • 形式上：A∖B={x∣x∈A 且 x∉B}

  • 其中 ∉ 表示”不是...的一部分”。

  • 这个符号表示我们定义了一个包含所有元素 x 的集合，使得 x 是 A 的一个成员但 NOT 是 B 的一个成员。

  • 示例：{1,2,3}∖{3,4,5}={1,2}

• 补集 ( Ac 或 A―)：集合 A 相对于全集 U 的补集是由 U 中所有不属于 A 的元素组成的集合。 全集 U 是所有可能元素的集合（取决于你工作的系统，例如整数）。

  • 形式上：Ac={x∣x∈U 且 x∉A}

  • 示例：如果 U={1,2,3,4,5} 并且 A={1,3,5}，那么 Ac={2,4}

  • 集合 A 的补集是差集运算的一个特殊情况，其中 B 是特定的——全集 U。

• 对称差 ( △ 或 ⊕)：集合 A 和 B 的对称差，记为 A△B，是由属于 A 或 B 但不属于它们的交集的元素组成的集合。

  • 形式上：A△B=(A∖B)∪(B∖A)=(A∪B)∖(A∩B)

  • 这个概念表示我们定义了一个包含 A OR B 中所有元素的集合，但排除了 A 和 B 中都存在的任何元素。

  • 示例：{1,2,3}△{3,4,5}={1,2,4,5}

笛卡尔积

两个集合 A 和 B 的笛卡尔积，记为 A×B，是由 all 有序对 (a,b) 组成的集合，其中 a∈A 且 b∈B。

• 形式上：A×B={(a,b)∣a∈A 且 b∈B}

• 示例：如果 A={1,2} 并且 B={x,y}，那么 A×B={(1,x),(1,y),(2,x),(2,y)}

关系

集合 A 和 B 之间的关系 是笛卡尔积 A×B 的一个子集。 它是有序对 (a,b) 的集合，其中 a∈A 且 b∈B。

关系的类型

1. 自反关系：如果对于每个元素 a∈A，(a,a)∈R，则集合 A 上的关系 R 是自反的。

   • 示例：整数上的“等于”关系：每个整数都等于它自身。

2. 对称关系：如果对于所有 a,b∈A，如果 (a,b)∈R，则 (b,a)∈R，则集合 A 上的关系 R 是对称的。

   • 示例：人之间的“兄弟姐妹”关系：如果 Sarah 是 Alice 的兄弟姐妹，那么 Alice 也是 Sarah 的兄弟姐妹。

3. 传递关系：如果对于所有 a,b,c∈A，如果 (a,b)∈R 并且 (b,c)∈R，则 (a,c)∈R，则集合 A 上的关系 R 是传递的。

   • 这意味着关系链接在一起。 如果 A 与 B 相关，并且 B 与 C 相关，那么 A 必须与 C 相关。

   • 示例：实数上的“大于”关系。 如果 a>b 且 b>c 那么 a>c

4. 等价关系：一种自反、对称和传递的关系。

   • 这创建了分组，其中一个组中的所有元素根据该关系被认为是“相同的”。

   • 示例：“同余模 n”是整数上的等价关系。

   • 等价关系将集合划分为等价类：不相交的子集（这些子集没有共同的元素），其中一个类中的所有元素都彼此相关。 例如，模 3 创建三个类：{0,3,6,...}, {1,4,7,...} 和 {2,5,8,...}。

函数

从集合 A 到集合 B 的函数是一种特殊的关系，其中 A 中的每个元素都与 B 中的恰好一个元素相关。

• 形式上：f:A→B 是一个函数，如果对于每个 a∈A，都存在唯一一个 b∈B 使得 f(a)=b。

• 集合 A 称为该函数的定义域，集合 B 称为上域。

函数的类型

1. 单射（一对一）：如果 A 中不同的元素映射到 B 中不同的元素，则函数 f:A→B 是单射的。

   • 形式上：对于所有 a1,a2∈A，如果 a1≠a2，则 f(a1)≠f(a2)。

   • 等价地：对于所有 a1,a2∈A，如果 f(a1)=f(a2)，则 a1=a2。

2. 满射（映上）：如果 B 中的每个元素都由 A 中的至少一个元素映射到，则函数 f:A→B 是满射的。

   • 形式上：对于所有 b∈B，都存在一个 a∈A 使得 f(a)=b。

3. 双射（一一对应）：一个既是单射又是满射的函数。

   • 双射函数确保上域中的每个元素都由定义域中的恰好一个元素映射到，反之亦然。

   • 所有双射函数都有逆函数。

接下来是什么？

在本系列的下一部分中，我们将探讨群论以及如何使用集合定义群。 这将帮助我们理解这些数学结构的性质，以便我们稍后了解它们如何在 Groth16 和 PLONK 等零知识证明协议中使用。

总结

• 集合论是数学的一个分支，研究对象的集合，这些对象称为集合

• 集合是不同元素的集合，没有重复

• 元素可以是任何对象（数字、字母等），只要每个对象都是唯一的

• 基数是指集合中元素的数量

• 集合的类型：

  • 有限集具有特定的、可数的元素数量
  • 可数无限集可以与自然数建立一一对应关系
  • 不可数无限集无法枚举（例如，实数）

• 关键集合关系：

  • 子集：如果 A 的每个元素也在 B 中，则 A ⊆ B
  • 真子集：当 A ⊆ B 且 A ≠ B 时，A ⊂ B
  • 空集 (∅) 是每个集合的子集
  • 幂集包含集合的所有可能子集

• 集合运算：

  • 并集 (∪)：任一集合或两个集合中的元素
  • 交集 (∩)：两个集合共有的元素
  • 差集 (\)：第一个集合中但不在第二个集合中的元素
  • 补集：全集的元素但不在给定的集合中
  • 对称差 (△)：任一集合中但不同时出现在两个集合中的元素

• 关系和函数：

  • 笛卡尔积从两个集合创建有序对
  • 关系是笛卡尔积的子集
  • 函数将域的每个元素映射到上域的恰好一个元素
  • 函数类型：单射（一对一）、满射（映上）、双射（都是）

• 集合论为理解和描述密码学和零知识证明中使用的数学结构奠定了基础。

• 在下一篇文章中，我们将使用这些知识来理解群论——如果我们将某些东西描述为一个群，这意味着什么？

参考

更喜欢通过视频学习？ 请查看此 YouTube 视频！

其他资源：

• RareSkills ZK Book
• 集合论 by geeksforgeeks.com
• UCL 的集合论简介

• 原文链接： cyfrin.io/blog/zk-math-1...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～