二元关系

Prerequisite　集合

关系

　　在 “集合” 中我们只关心了集合的基数，即集合中元素的数目．在这种语境下，任何两个元素数量相同的集合都可以看作是同一个集合．但是仅仅讨论集合的基数未免太过单调，缺少了很多有意思的理论，于是我们希望在集合的元素之间建立一些结构，来进行更细致的划分和研究．

　　 关系（relation）是集合上最基础的一种结构．给定一个关系，我们就可以讨论一些元素之间是否满足这个关系．比如说，如果取一家三口构成一个集合，$\sim$ 代表的是 “年龄大于”，那么我们可以说 “爸爸对于孩子具有这个关系”，但是反过来 “孩子对于爸爸不具有这个关系”．从这个例子可以看出，关系的表达方式很灵活，而且可以是有方向性的．讨论关系时，我们唯一关心的是给定元素之间是否具有这样的关系．

　　关系可以用在两个元素之间，也可以用在三个元素之间，甚至可以用在不特定的元素之间．

二元关系

　　在绝大多数数学和物理领域，我们只关心集合上的二元关系（binary relation）．如果 $\sim$ 是在集合 $A$ 上定义的一个二元关系，那么任意给定两个元素，我们都可以讨论它们之间是否具有这种关系，但如果给定三个元素，讨论就没有意义了．比如，如果 $\sim$ 的定义是 “年龄大于”，那么把三个人的年龄都拿过来比较就没有意义；不过，如果 $\sim$ 的定义是 “比后面两个人的年龄都大”，那么 $\sim$ 就可以用在三个人身上．

　　对于集合 $A$ 上的二元关系 $\sim$，如果 $x, y\in A$ 满足这个关系，我们可以把这句话表述为 $x\sim y$．如果不满足，则可以表述为 $x\not\sim y$．用这样简洁的表示方法，我们可以把以上 “年龄大于” 的关系表述如下：

\begin{equation} \text{爸爸}\sim\text{孩子} \qquad \text{妈妈}\sim\text{孩子} \qquad \text{孩子}\not\sim\text{爸爸} \qquad \text{孩子}\not\sim\text{妈妈} \qquad \end{equation}

爸爸和妈妈之间，在没有进一步信息的情况下，无法判断是否满足这个关系，但这个关系是存在的．也就是说，元素间的关系一共有两种状态：满足和不满足．

等价关系

　　最基础的一类关系，是等价关系（equivalence）．在集合 $A$ 上定义的关系 $\sim$ 是一个等价关系，要求满足条件：

自反性：$\forall x\in A, x\sim x$；
对称性：$\forall x, y\in A, x\sim y \Rightarrow y\sim x$；
传递性：$\forall x, y, z\in A, x\sim y, y\sim z\Rightarrow x\sim z$．

　　如果把 “具有关系 $\sim$” 看成是两个元素间相互连接（没有方向性，因为对称性），传递性保证了当多个元素相连时，这些元素也两两互联；自反性甚至保证了每个元素必然和自身相连．由此一来，我们可以根据等价关系把集合 $A$ 划分成等价类（equivalence class），每个等价类都是 $A$ 的一个子集，所包含的元素彼此相连．

　　等价类的划分是数学中非常重要的思维方法，它可以将每一个等价类中的元素都看成是无差别的，大大简化一个集合的复杂程度．有了等价关系后，我们可以用相应的等价类来组成一个新的集合，这样的集合被称作商集（quotient set）．和原来集合中的元素不一样，商集中的元素是原集合中的子集．

　　作为例子，我们取全体非负整数的集合 $\mathbb{Z}$，并在上面定义关系 $\sim$ 为 “两数的差是 3 的倍数”，那么容易验证，$1\sim4, 7\sim304, 0\not\sim 77, 77\not\sim 1$．利用这个等价关系，我们可以把非负整数集合划分成三个等价类，分别是 $\{0, 3, 6, 9, 12\cdots \}$，$\{1, 4, 7, 10, 13\cdots\}$ 和 $\{2, 5, 8, 11, 14\cdots\}$．这样，我们可以得到一个含有三个元素的商集，用数学专业术语来说，叫做集合 $A$ 模去关系 $\sim$ 所得的商集．这里的模（mod）的意思来自于 “除法”，在群论中会看到为什么用除法来命名商集．