4.2　何谓相等

我们在上一节看到，两个集合可以通过映射连接起来。但是，映射是一种很特殊的连接，其定义域中的每个元素只能有一个像。现实中，我们不难想见两个集合间会有更复杂的连接方式。比如，令 N 为世界上全部国家的集合。若我们考察国家之间的贸易关系，想知道每一个国家的最大贸易出口国，显然这个对应是一个从 N 到 N 的映射（未必是单射，也未必是满射）。但是，若考虑国家之间的外交关系的话，情况就不同了。显然，任何一个国家都能与别的不止一个国家邦交。这样一种多对多的连接，似乎是无法用一个从 N 到 N 的映射来表达的 ^[4] 。于是，我们有必要引入一种更加一般的集合间 关系 。

定义4.13 集合 X ₁ ,X ₂ ,… ,X _n 间的一个 关系 （relation）是它们的笛卡儿积 X ₁ × X ₂ …× X _n 的一个子集。若 X = X ₁ =…= X _n ，我们称该关系为集合 X 上的一个 n 元关系。特别的，当 n =2时，称其为 X 上的一个 二元关系 （binary relation）。

为什么这个定义描述了我们通常所说的“关系”呢？我们来看几个例子。

例子4.14 假设我们有3个国家 N ={魏,蜀,吴}，彼此之间都在打仗。于是，这层战争关系可以用如下 N × N 的子集来表达：

战争={（蜀,吴）,（吴,蜀）,（魏,吴）,（吴,魏）,（魏,蜀）,（蜀,魏）}

感觉重复了？为啥（蜀,吴）和（吴,蜀）要写两次呢？因为打仗是互相的，但是笛卡儿积是有顺序的。若将（ a,b ）解读为 a 在和 b 打仗，那反过来， b 也在和 a 打仗，故需要用另一个元素（ b,a ）来表示。

例子4.15 假设有三个人 P ={小王,小明,小花}，他们之间有一些说不清的暧昧关系。小王喜欢小明，小明喜欢小花，小花不但自恋还很花心，喜欢小王小明两个人。这个喜欢关系便是集合 P × P 的一个子集：

喜欢={（小王,小明）,（小明,小花）,（小花,小王）,（小花,小明）,（小花,小花）}

不难看出，喜欢就比结盟来的随意多了，不但能自恋，还可能构成三角恋。让我们再来看几个数学上常见的关系。

例子4.16 下述我们常见的符号都是集合上的二元关系。

·　小于 < 是 N 上的一个二元关系；

·　包含⊂是2 ^N 上的一个二元关系；

·　等于=是 N 上的一个二元关系。

你可能要说了，关系是笛卡儿积的子集，是集合，可我们平时写的“1 < 2”，怎么看这个“ < ”也不像是一个集合呀。其实，这只不过是一个符号改写罢了。一般的，若 R 是一个二元关系，我们记

xRy :=（ x,y ）∈ R

也即，1 < 2是一个缩写，其表示（1,2）属于 < 代表的集合。

在集合上众多可能的关系中，有一种关系我们尤为关心，那就是描述“等价”的关系。什么叫等价？即在某种意义下“被视为等同”。如果我们只是想区别人跟猫，那么你我虽是完全不同的个体，但当聚焦在“是人”的意义下来看待时，那就是等同的了，都不是猫。显然，不是随便一个关系都能称得上等价关系的，它必须要满足一些符合直观的性质。

定义4.17 令 X 为一个集合。我们称其上的一个二元关系 ∼ 是一个 等价关系 （equivalence relation），如果对于任意 a,b,c ∈ X ，以下三点成立：

· 自反性 （reflexive）： a ∼ a ；

· 对称性 （symmetric）： a ∼ b 当且仅当 b ∼ a ；

· 传递性 （transitive）：如果 a ∼ b 以及 b ∼ c ，那么 a ∼ c 。

打仗是等价关系吗？前面说过，打仗是相互的，对称性满足。就算我们勉强接受窝里斗算自己和自己打仗，让它满足了自反性，但俗话说得好，敌人的敌人是朋友，传递性就显然未必满足了。所以战争不是一个等价关系。

喜欢呢？姑且认为自恋算是自己喜欢自己，满足了自反性吧。对称性呢？我喜欢你，你就一定喜欢我吗？显然不一定，不然世间就没有那么多悲伤与遗憾了。传递性呢？我喜欢你，你喜欢他，于是我喜欢他？我可不想喜欢他！所以喜欢也不是一个等价关系。

那现实中有等价关系的例子吗？当然，比如血缘关系。我和我自己显然可以被认为有血缘关系。我和你有血缘，显然意味着你和我有血缘。最后，我和你有血缘，你和他有血缘，那我和他必然也有血缘。于是血缘关系是一个等价关系。

再来看看数学中的例子。自然数间的小于 < 是吗？感觉不是吧。它自反性就不满足。那我们放宽一点，小于等于≤呢？自反性满足了，传递性也满足，但是对称性显然不满足。所以它们都不是等价关系。

自然数间的等于=呢？听名字就觉得像。显然， a = a ，自反性成立。 a = b 当且仅当 b = a ，故对称性成立。 a = b 、 b = c 合在一起可知 a = c ，故传递性成立。于是，等于是一个等价关系。

在第2章的脚注38中我们提到过，表达相等其实涉及三种概念： 相同 （identity）、 等价 （equivalence）与 外延 （extensionality），这里不妨简单说两句。首先，相同是比等价更强的要求。哲学家们总结了 如下原则：

原则4.18（ 不可分者同一性原理 Principle of Identity of Indiscernibles） 两个事物是相同的当且仅当一方满足的任何性质另一方亦满足。

写成形式语言的话可能更加一目了然一些，不过得借助二阶逻辑来谈论“任意谓词”：

概念4.19 形式上，我们说两个变量 x 和 y 代表了相同的对象 ，如果对任意一元谓词 P 均有 P （ x ）↔ P （ y ）。

x = y :=∀ P : P （ x ）↔ P （ y ）

直观来说，两个东西若是相同的，它们应能在 任何 场合中随意替换彼此。举个例子，考察下面这个分数加法：

没问题吧。我们都知道1/3“等于”2/6，替换进去，我们得到

显然也不错，小学加法嘛。其实，这背后我们是考察了命题

并且发现 P （1/3）与 P （2/6）同为真，很好。但是“相同”可是需要对 任意 命题 P 都成立 P （ x ）与 P （ y ）同真同假！下面这个命题呢？

Q （ x ）: x 的分子分母之和为4

显然 Q （1/3）为真，但是 Q （2/6）为假！于是，1/3与2/6是“不同”的，仅当我们在讨论算术时，它们是“等价”的。

在判定相同时，我们需要进行替换与代入，这便又涉及 外延 （extension）与 内涵 （intension）的概念了。我们来看这个推理：“令 n 等于太阳系行星的个数，开普勒 （Kepler）不知道 n> 6，现代科学告诉我们 n =8，于是开普勒不知道8 > 6。”何其荒谬！可问题出在哪里呢？如果考虑命题

P （ x ）：开普勒不知道 x> 6

那么 P （太阳系行星的个数）是真的，但是 P （8）就是假的了！虽然“太阳系行星的个数” 等于 8，但是我们不能将它们简单粗暴地直接替换代入 P ！我们称这种 不允许 直接替换变量的情形为 内涵的 （intensional）。反之，若一个陈述允许将符号直接进行替换，我们便称之为 外延的 （extensional）。于是，用“8”替换“太阳系行星的个数”代入 P （ x ）就是一个内涵的情形。

进一步究其原因，会发现内涵的情形中，两个貌似相同的对象其实是不同的，在定义它们的符号的纯形式之外其实有着一个隐含的等价关系，它导致这些对象被认为是相等的。比如“太阳系行星的个数8”与“自然数8”，在我们的认知中都是8，那是因为我们的经验诱导了一个等价关系，在其下二者等价，被我们都称做[8]，如图4.4。但在开普勒的认知中，它们是两个完全无关的不同概念。所以，我们不能将此8替换为彼[8]。反过来，在外延的情形中，一段描述最终所框定的那些存在彼此并非隐式地等价，它们就是相同。比较难以理解？我们来看一个例子。考虑集合

我们证明过若一个自然数的平方是偶数，那它自己一定也是偶数（断言2.15）。于是不难得到 P 和 Q 包含相同的自然数，是相等的。等一下！要知道，此时我们是在外延的意义下说 P 和 Q 相等。此时 P 中的4就是 Q 中的4， Q 中的8就是 P 中的8，任何关于 P 中16的命题，同样对 Q 中的16成立……它们中的元素并非因某个隐藏着的等价关系而相等，它们就是相同的对象，可以在任意场合随意替换彼此。所以，这也正是几乎所有讲集合论的书的第一条公理都叫 外延公理 的原因：

概念4.20 （ 外延公理 Axiom of Extensionality）　两个集合相等当且仅当它们包含的元素相同。

∀ a :∀ b :（∀ x :（ x ∈ a ↔ x ∈ b ）↔ a = b ）

外延公理便是在强行 规定 当我们讨论集合时，一切语境都是外延的，集合描述框定的貌似相同的对象并非隐含地等价，它们就是相同的对象。当然，本书并未囊括外延公理，是因为在其定义中需要等号，但我们没有为谓词逻辑添加等号，而是在集合论中将等号作为定义给出（定义3.17）。

说了这么多，其实不用纠结与害怕，用我们朴素的直觉来区分集合的相等与等价就足够了！集合相等就是它们的元素一模一样，那集合等价做何解呢？某种意义上，在忽略掉元素之间的具体差异后，集合内蕴的性质就只剩下一个了——其元素的“个数”，于是不同集合只要“大小”一样，便在集合意义上是等价的。何谓两个集合“大小一样”？即它们之间有个一一对应 ^[5] ！

定义4.21 如果两个集合之间存在一个双射，我们便称它们是 同构的 （isomorphic）。

不难看出“ A 与 B 是同构的”是集合之间的一个等价关系。

作为表达特定意义下的相等，等价关系的一个重要功能是，忽略元素间无关紧要的差异，即那些在等价关系考虑之外的性质，仅在我们关心的意义下区分它们。

定义4.22 令 X 是一个集合， ∼ 为其上一个等价关系。对任意元素 x ∈ X ，其在 ∼ 下的 等价类 （equivalence class）是由 X 中所有与 x 等价的元素构成的集合

[ x ]:={ a ∈ X | a ∼ x }

所有 X 中元素等价类的全体构成一个新的集合

称为 X 在 ∼ 下的 商集 （quotient set）。

一般我们也将商集读作“ X 模掉（modulo）等价关系 ∼ ”。等价类与商集的概念怎么强调都不为过，因为其关乎了抽象最为核心的目的：抹去表象，保留本质。在我们接下来的旅程中，商集将扮演非常重要的角色。

让我们来看个例子。写作此书时，新型冠状病毒肺炎正在肆虐，便就用它来举例吧。现在我们想要研究新冠肺炎的易感人群。令 P 为所有中国人构成的集合，这是一个有近14亿元素的庞大有限集。首先，我们想考察性别是否与感染相关，这其实就是构造了等价关系：

a ∼ ₁ b : a 与 b 性别相同

并考察病毒在集合 P 模掉 ∼ ₁ 后的商集上的表现，其只剩下两个元素了：

P / ∼ ₁ ={[ m ],[ f ]}

其中 m ∈ P 为随便一个男性， f ∈ P 为随便一个女性。等价类[ m ]和[ f ]都是具有大约7亿个元素的集合，其中包含各行各业的老百姓与王侯将相，但这些身份、地位、职业的差异都被忽略了。在 P / ∼ ₁ 中就两个元素，男性全体和女性全体。

可能研究后发现，病毒不但和性别有关，还和血型有关。于是我们进一步考虑等价关系：

a ∼ ₂ b : a 与 b 性别相同且血型相同

P 模掉 ∼ ₂ 后就有8个元素了：

P / ∼ ₂ ={[ m _A ],[ m _B ],[ m _AB ],[ m _O ],[ f _A ],[ f _B ],[ f _AB ],[ f _O ]}

其中 m _A ,m _B ,m _AB ,m _O ∈ P 为任意4名具有A,B,AB,O型血的男性， f _A ,f _B ,f _AB ,f _O 为任意4名具有A,B,AB,O型血的女性。

相信你已经看出来了，等价关系起到了一个 聚类 的作用。它忽略元素间不相关的差异，将被视为等价的元素聚在一起，视为一个整体，也即一个类，并汇总这些类构成商集，如图4.5。

不过这里有一个小问题。上面的例子中， m 和 f 是 随便 选择的一个男性和一个女性。真的能这么随便吗？如果我换一个男性 m′ ，它们各自的等价类[ m ]与[ m′ ]相同吗？

命题4.23 令 X 是一个集合， ∼ 为其上一个等价关系。对任意元素 a,b ∈ X ，若 a ∼ b ，则[ a ]=[ b ]。

这个命题表明，我们可以任意选取等价类中元素来 代表 这个等价类，这个被选出的元素被称做这个等价类的 代表元 （representative）。

命题4.23的证明 我们想要证明两个集合[ a ]和[ b ]相等。取任意 ^[6] x ∈[ a ]，由等价类的定义我们有 x ∼ a 。由假设 a ∼ b 以及等价关系的传递性我们得到 x ∼ b ，于是由[ b ]的定义可知 x ∈[ b ]，进而[ a ]⊂[ b ]。反之，由假设 a ∼ b 以及等价关系的对称性我们得到 b ∼ a ，进而同理得到[ b ]⊂[ a ]。综上可得[ a ]=[ b ]。　　　　　　　　　　　　　　　　　　　　□

代表元的问题解决了，我们可以随便选！不过还有一个小问题，直观上我们按照某些性质聚类一个集合，当然不希望有遗漏和重复，一定要将每一个元素都恰好仅放到某一类中。比如上面按血型聚类的例子其实就有点问题，因为熊猫血的人似乎无法被归到上述任何一类。不过这也没关系，因为他们将自行组成一个新的类。于是问题便来了，我们在数学上定义出的等价关系与商集，能确保这个直观的要求么，即确保任何元素都被且仅被分到了一类吗？

命题4.24 令 X 是一个集合， ∼ 为其上一个等价关系。对任意元素 a ∈ X ，存在唯一 x ∈ P / ∼ ，使得 a ∈ x 。

证明 由等价关系的自反性可知 a ∈[ a ]，故存在性得证。令 x,y ∈ P / ∼ 使得 a ∈ x 且 a ∈ y ，由命题4.23可知 x = y =[ a ]，故唯一性得证。　　　　　□

命题4.23的证明用到了等价关系的对称性与传递性，命题4.24用到了自反性。于是我们看到，等价关系定义中的三个性质是缺一不可的，它们恰好充分不多不少，合在一起保证了：

洞察4.25 等价关系描述了对集合元素进行分组聚类的操作，使得任何元素属于且仅属于一类，每一类可随意选取其中元素作为代表元。 ZlGraRyjMdusLAS13LHtjB6YANn666DnAZKly2CtHdgr9mMqJHgBnn9asG17bmiO