下载掌阅APP，畅读海量书库
立即打开
我们在上一节看到，两个集合可以通过映射连接起来。但是，映射是一种很特殊的连接，其定义域中的每个元素只能有一个像。现实中，我们不难想见两个集合间会有更复杂的连接方式。比如，令 N 为世界上全部国家的集合。若我们考察国家之间的贸易关系，想知道每一个国家的最大贸易出口国，显然这个对应是一个从 N 到 N 的映射（未必是单射，也未必是满射）。但是，若考虑国家之间的外交关系的话，情况就不同了。显然，任何一个国家都能与别的不止一个国家邦交。这样一种多对多的连接，似乎是无法用一个从 N 到 N 的映射来表达的 [4] 。于是，我们有必要引入一种更加一般的集合间 关系 。
定义4.13 集合 X 1 ,X 2 ,… ,X n 间的一个 关系 （relation）是它们的笛卡儿积 X 1 × X 2 …× X n 的一个子集。若 X = X 1 =…= 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]。反过来，在外延的情形中，一段描述最终所框定的那些存在彼此并非隐式地等价，它们就是相同。比较难以理解？我们来看一个例子。考虑集合
图4.4内涵与外延
我们证明过若一个自然数的平方是偶数，那它自己一定也是偶数（断言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 ∼ 1 b : a 与 b 性别相同
并考察病毒在集合 P 模掉 ∼ 1 后的商集上的表现，其只剩下两个元素了：
P / ∼ 1 ={[ m ],[ f ]}
其中 m ∈ P 为随便一个男性， f ∈ P 为随便一个女性。等价类[ m ]和[ f ]都是具有大约7亿个元素的集合，其中包含各行各业的老百姓与王侯将相，但这些身份、地位、职业的差异都被忽略了。在 P / ∼ 1 中就两个元素，男性全体和女性全体。
可能研究后发现，病毒不但和性别有关，还和血型有关。于是我们进一步考虑等价关系：
a ∼ 2 b : a 与 b 性别相同且血型相同
P 模掉 ∼ 2 后就有8个元素了：
P / ∼ 2 ={[ 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 ]。
图4.5商集
这个命题表明，我们可以任意选取等价类中元素来 代表 这个等价类，这个被选出的元素被称做这个等价类的 代表元 （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 等价关系描述了对集合元素进行分组聚类的操作，使得任何元素属于且仅属于一类，每一类可随意选取其中元素作为代表元。