二元关系

贡献者： hfb25; JierPeter; addis; xiaokuc

预备知识　集合

1. 关系

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

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

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

2. 二元关系

　　在绝大多数数学和物理领域，我们只关心集合上的二元关系（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}

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

　　在数学上，二元关系的严格定义是:

定义 1　二元关系

　　设 $A \times A$ 的子集 $R$，如果集合 $A$ 中的两个元素 $a,b$ 满足 $(a,b) \in R$ ,那么就称 $a,b$ 满足关系 $R$。也称 $a,b$ 是 $R-$ 相关的，并且记作 $aRb$.

　　下面是一个简单的例子：

例 1　

　　设集合 $A=\{1,2\}$ 上的关系 $R$ 为 $a< b,\ \forall (a,b)\in A^2$.

　　集合 $A$ 的笛卡尔积为：

\begin{equation} A^2 = \{(1,1),(1,2),(2,1),(2,2)\}~. \end{equation}

那么就有：

\begin{equation} R=\{(1,2)\}\subset A^2~. \end{equation}

　　我们注意到在 $\mathbb{R}$ 上，装备着小于关系和大于关系，它们间有一种对偶的联系，因此我们引入对偶关系来描述这种联系。

3. 对偶关系

定义 2　对偶关系

　　设 $R$ 是非空集合 $A$ 上的一个二元关系. 我们定义 $A$ 上的另一个关系 $R^{d}$ 如下:

　　 $(x, y) \in R^{d} \Leftrightarrow(y, x) \in R~.$

　　我们称 $R^{d}$ 是 $R$ 的对偶关系

　　对偶关系描述的是二元关系的对称性，同时容易验证,存在着一些二元关系，它们的对偶关系是自身。

4. 等价关系

　　最基础的一类关系，是等价关系（equivalence），它也是一类满足对偶关系是自己的关系（即对称性）

定义 3　等价关系

　　在集合 $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）的意思来自于 “除法”，在群论中会看到为什么用除法来命名商集。

未完成：以下为回收内容

5. 序关系

　　另一类比较基础的关系是序关系（ordering relation）。在集合 $A$ 上定义的关系 $\prec$（一般也可以写成 $\leq$ 或 $\leqslant$）是一个序关系，要求满足条件：

自反性：$\forall x\in A,x\prec x$；
反对称性：$\forall x,y\in A,\ x\prec y,\ y\prec x \Rightarrow x = y $；
传递性：$\forall x,y,z\in A,\ x\prec y,\ y\prec z \Rightarrow x\prec z $。

　　序关系是比较基础的一类关系，它在数学各个学科中广泛运用。

　　序关系也是序论的中心课题。接下来，我们将主要探讨序关系。

致读者：小时百科一直以来坚持所有内容免费，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 10 元，我们一个星期内就能脱离亏损，并保证在接下来的一整年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。